精确变更算法 [英] Exact Change Algorithm

问题描述

我正在尝试编写一种算法，以检查在有限数量的不同值的硬币（特别是Quarters，Dimes，Nickels和Pennies）的情况下是否有可能实现零钱。我已经看到了许多建议的解决方案包括此处的堆栈溢出以及 freeCodeCamp ，但是这两种解决方案都有相同的问题，有时会产生

I'm trying to write an algorithm that checks if it is possible to get exact change given a limited number of coins of different values, specifically Quarters, Dimes, Nickels, and Pennies. I have seen many proposed solutions including here on stack overflow as well as one from freeCodeCamp but both of these solutions share the same problem in that sometimes produce false negatives.

注意：这不是产生变化的问题，因为我对无限池中的最小硬币数量不感兴趣，即使现有池可以支持确切数量的硬币也是如此。

NOTE: this is not the Change-making problem as I am not interested in the minimum number of coins from an infinite pool, just if the existing pool can support an exact quantity.

我见过的常用算法如下：

The algorithm I have seen commonly used is as follows:

• 在池中找到价值低于目标金额的最高硬币


• 减去池中的硬币之一，然后从目标金额中减去其值


• 继续，直到目标金额为0（返回true或所需硬币列表），或者直到没有可用币值小于目标的硬币（返回false）

但是这种方法存在一个问题：如果解决方案需要高价值的低面额硬币，即使可能存在有效的解决方案，也会返回false。

But there is a problem with this approach: If a solution requires a high value of low denomination coins, it will return false even though there may be a valid solution.

这里是该算法的一些代码（从前面链接的堆栈溢出文章中适应了我的目的，因此可能很乱）

Here is some code of this algorithm (adapted for my purposes from that stack overflow article linked earlier so it may be messy)

values = [25, 10, 5, 1]

def exact_change(target_amount, L, ret = None):
    if ret == None:
        ret = [0] * len(L)

    for i in range(len(L)):
        if L[i] == 0:
            continue
        if values[i] == target_amount:
            ret[i] += 1
            return ret
        else:
            if values[i] < target_amount:
                L[i] -= 1
                ret[i] += 1
                return exact_change(target_amount-values[i], L, ret)
    else:
        return False


print(exact_change( 48, [1, 2, 6, 3] ))
# [1, 2, 0, 3] correct
print( exact_change( 45, [2, 1, 1, 4] ))
# False correct
print(exact_change( 285, [100, 10, 10, 100] ))
# [11, 1, 0, 0] correct
print(exact_change( 65, [2, 4, 1, 0] ))
# [2, 1, 1, 0] correct
print(exact_change( 65, [2, 6, 0, 0] ))
# False incorrect! [1, 4, 0, 0] would work

如果您从要么先寻找价值较低的硬币。我只是还没有找到更好的算法，还是一个开放的问题？我可以通过检查将产生目标值的硬币的每种组合，并查看给定的池是否可以实现这种组合，但对于较大的值似乎效率低下，来蛮力解决问题。

This approach doesn't work if you start by looking for lower valued coins first either. Is there a better algorithm I simply haven't found yet or is this an open problem? I can brute force a solution by checking each combination of coins that would produce the target value and seeing if that combination is possible with the given pool but that seems inefficient for large values.

推荐答案

您当前的算法存在的问题是，它只能尝试递归一次。无论该递归找到了什么（有效的解决方案或失败），该结果都会无条件返回。尽管还有其他一些算法可能会有所不同，但是您可以对当前代码进行少量更改以通过添加回溯来使其正常工作。

The problem your current algorithm has is that it only ever attempts to recurse once. Regardless of what that recursion finds (either a valid solution, or a failure), that result is returned unconditionally. While there are some other algorithms that would work differently, you can make a small change to your current code to make it work by adding backtracking.

回溯步骤在每次执行之后进行递归。首先，您检查递归是否成功（例如，找到了有效的结果）。如果是这样，您将像平常一样返回该结果。但是，如果操作失败，则需要撤消对问题状态所做的更改（在这种情况下，撤消对 L 和 ret的更改） ，然后继续尝试另一种硬币面额。

The backtracking step happens after each recursion. First you check if the recursion was successful (e.g. it found a valid result). If so, you return that result like normal. However, if it was unsuccessful, you need to undo the changes you made to the problem state (in this case, undo the changes to L and ret, and then go on to try another coin denomination.

虽然您的代码还有另一个问题，您的代码没有任何办法避免每次函数递归时都检查相同的起始面额，因此对于某些输入，您将一遍又一遍地尝试相同的不良解决方案。一种避免重新检查相同硬币的方法是将起始索引与其他参数一起传递，并且

There's another issue with your code though. Your code doesn't have any way to avoid checking the same starting denominations every time your function recurses, so for some inputs you'll keep trying the same bad solutions over and over. A way to avoid reexamining the same coins is to pass a start index along with the other arguments, and not look at the coins before that index at all.

def exact_change(target_amount, L, start_index=0, ret=None):
    if ret == None:
        ret = [0] * len(L)

    for i in range(start_index, len(L)): # start at start_index
        if L[i] == 0:
            continue
        if values[i] == target_amount:
            ret[i] += 1
            return ret
        elif values[i] < target_amount:  # no need for the extra indentation of else: if ...:
            L[i] -= 1
            ret[i] += 1
            result = exact_change(target_amount-values[i], L, i, ret) # pass i as start_index
            if result:     # check the result to make sure it was successful before returning
                return result
            L[i] += 1      # backtrack if it was not
            ret[i] -= 1
    else:
        return False   # None might be a more natural value to return here

请注意，如果需要，可以避免在递归步骤中修改 L （并且需要在回溯时撤消更改）。只需将 L [i] == 0 测试更改为 L [i] == ret [i] 。

Note that if you wanted to, you could avoid modifying L during the recursive step (and needing to undo the change when backtracking). Just change the L[i] == 0 test to L[i] == ret[i] instead.

这篇关于精确变更算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！