代码之家 › 专栏 › 技术社区 › edmamerto

换币递归算法解卷

recursive-datastructures recursion algorithm

-2

edmamerto · 技术社区 · 6 年前

我正在努力 unwind 这个 recursive 在此中的功能 algorithm .硬币兑换问题:给定目标金额n和列表 array 在不同的硬币价值中,兑换金额所需的最少硬币是多少。

def rec_coin(target,coins):

    # Default to target value
    min_coins = target

    # Check to see if we have a single coin match (BASE CASE)
    if target in coins:
        return 1

    else:

        # for every coin value that is <= than target
        for i in [c for c in coins if c <= target]:

            # Recursive Call (add a count coin and subtract from the target) 
            num_coins = 1 + rec_coin(target-i,coins)

            # Reset Minimum if we have a new minimum
            if num_coins < min_coins:

                min_coins = num_coins

    return min_coins

# rec_coin(63,[1,5,10,25])
# 6

这是我拆开后想到的

1 + 63-1 coins + 62-1 + 61-1 and so on..

为什么需要添加1?取消递归的正确方法是什么

1 回复 | 直到 6 年前

1

trincot Jakube 6 年前

您提供的代码效率很低。为了找到63的解,假设它将首先以最小硬币(即1)的步骤递归到目标量。然后,在多次回溯并尝试使用其他硬币后,它最终回溯到最外层,并尝试使用价值为5的硬币。现在递归又开始了,就像以前一样,添加了值为1的硬币。但问题是,这个中间值(63-5)之前已经被访问过(在选择硬币1后深入5层),需要进行大量函数调用才能得到该值的结果58。然而,算法将忽略这一点,并再次执行所有这些工作。

一种常见的解决方案是动态编程,即记忆早期发现的解决方案,以便无需额外工作即可重用。

我将在这里介绍一种自下而上的方法:它首先检查只需一枚硬币即可获得的所有金额。这些金额被放入队列中。如果目标在其中,那么答案是1。如果没有,则通过将所有可能的硬币添加到每个硬币来处理队列中的所有金额。有时会找到以前访问过的值,在这种情况下,它不会被放入下一个队列,但在其他情况下,它会被放入下一个队列。如果现在目标值在该队列中,那么您知道只需2个硬币即可达到目标。

这一过程在循环中继续,实际上这只是树中的广度优先搜索,其中数量是节点,边表示通过向其中添加一枚硬币可以从另一个数量中获得一个数量。搜索从表示数量为0的节点开始。

下面是代码:

def rec_coin(target, coins):
    visited = set() # Amounts that we have already achieved with a minimal number of coins
    amounts = [0] # The latest series of amounts all using an equal number of coins
    for min_coins in range(1, target+1):
        next_amounts = []
        for amount in amounts:
            for coin in coins:
                added = amount + coin
                if added == target: 
                    return min_coins
                if not added in visited:
                    visited.add(added)
                    next_amounts.append(added)
        amounts = next_amounts

print (rec_coin(63,[1,5,10,25]))