时间戳

首页 > 解决方案 > 硬币找零递归算法展开

algorithm - 硬币找零递归算法展开

问题描述

我正在尝试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？展开递归的正确方法是什么

标签： algorithmrecursionrecursive-datastructures

解决方案

您提供的代码效率非常低。为了找到金额为 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]))

推荐阅读