python - 精确变化算法

Question

我正在尝试编写一种算法，检查在给定数量有限的不同面值硬币(特别是 25 美分、10 美分、5 分硬币和 1 美分硬币)的情况下是否有可能得到准确的找零。我已经看到许多建议的解决方案 including here on stack overflow以及来自 freeCodeCamp 的一个但这两种解决方案都有相同的问题，即有时会产生漏报。

注意:这不是 Change-making problem因为我对无限池中硬币的最小数量不感兴趣，只要现有池可以支持确切数量即可。

我见过常用的算法如下:

• 找到池中值(value)小于目标数量的最高硬币
• 减去池中的这些硬币之一，并从目标数量中减去它的值(value)
• 继续直到目标数量为 0(返回 true 或所需硬币列表)或直到没有可用的硬币值(value)小于目标(返回 false)

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

这是该算法的一些代码(出于我的目的改编自之前链接的那篇堆栈溢出文章，因此它可能很困惑)

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

如果您首先寻找值(value)较低的硬币，则此方法也不起作用。是否有更好的算法我还没有找到，或者这是一个悬而未决的问题？我可以通过检查将产生目标值的每个硬币组合并查看该组合是否可以用于给定的池来强制解决方案，但对于大值来说这似乎效率低下。

Answer 1

您当前的算法存在的问题是它只尝试递归一次。无论递归找到什么(有效解决方案或失败)，都会无条件返回该结果。虽然还有一些其他算法的工作方式不同，但您可以通过添加回溯对当前代码进行小的更改以使其工作。

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

但是您的代码还有另一个问题。每次函数递归时，您的代码都无法避免检查相同的起始面额，因此对于某些输入，您将一遍又一遍地尝试相同的错误解决方案。避免重新检查相同硬币的一种方法是将起始索引与其他参数一起传递，并且根本不查看该索引之前的硬币。

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]。