分而治之的递归解决方案进行更改

Question

我正在尝试实现一个分而治之的程序，当给定一个硬币集 c = {c0, c1,...,cn} 和金额 A 时，它会找到可以支付 A 的多种不同方式，以及函数递归了多少次。

我的想法是做这样的事情：

callsMade = 0
coins = [1,5,10,25]

def makeChange(A, c):
    global callsMade
    callsMade += 1
    if(A == 0):
        return 1
    if(A < 0):
        return 0
    combos = 0
    for i in range(len(coins)):
        combos += makeChange(A - coins[i], i)
    return combos

其中 A 是传入的金额，c = len(coins)-1。 不过，这段代码的行为并不符合我的预期。我的思考过程是循环遍历硬币数组，用数组中该位置的硬币减去当前金额，并使用数组中较低的金额和下一个硬币递归调用 makeChange 函数，然后将全局调用每个增加 1时间。

使用硬币集 = [1,5,10,25] 和数量 A = 200，组合数量应为 1463，调用次数约为 1500。

Answer 1

递归关系看起来像这样（为了简洁，我删除了调用计数器）：

def makeChange(A, coins, k=0):
    if A == 0: return 1
    if A <  0: return 0
    return sum(makeChange(A - coins[i], coins, i) for i in range(k, len(coins)))

也就是说，你不要考虑比你已经拿走的硬币更小的硬币，否则你会得到像

[1, 1, 5]

和

[1, 5, 1]

这样的组合。这样，我得到了 1463 个

makeChange(200, (1,5,10,25))

组合，总共 111491 个调用——比您预期的要多一些。

请注意，此函数将多次计算许多组合。例如，您可以通过

A=194

或通过

[1,5]

到达

[1,1,1,1,1,1]

，依此类推，但是

makeChange(194, coins, k=1)

的结果对于这两种方式是相同的。您可以使用

functools.lru_cache

自动记住这些值。这样，只需拨打 801 电话即可获得相同的结果。

@functools.lru_cache(None)
def makeChange(A, coins, k=0):
    # same as above

（为了记忆，您必须包含

coins

作为参数（作为

tuple

，而不是

list

，以便可散列），否则它会将结果重复用于另一组硬币。）

Answer 2

基本思想是正确的，但你需要考虑一些递归问题以及你想要算作正确答案的问题。

如果你简单地开始，你可以问

[1,5,10,25]

的多少个组合应该等于

6

：

应该是3吗：

[1, 1, 1, 1, 1, 1], [5, 1], [1, 5]

？
或 2：

[1, 1, 1, 1, 1, 1], [1, 5]

？

两个对我来说最有意义。为此，您需要将硬币数组的子集传递回递归，因此当您在 for 循环中查看 5 时，您不会再次考虑

[5, 1]

— 假设此时您已经数过

[1, 5]

。不要传递未使用的

c

参数，而是传递

coins

列表。然后在循环中管理该列表。这里我添加了一个额外的参数

cur

来收集组合，只是为了帮助检查工作。如果您只想计数，则不需要它。

def makeChange(A, coins, cur = None):
    ''' This will also collect the combinations to check the work'''
    if cur is None:
        cur = []
    global callsMade
    callsMade += 1
    if(A == 0):
        print(cur)
        return 1
    if(A < 0):
        return 0
    combos = 0
    for i, coin in enumerate(coins):
        if coin > A: # don't bother if coin is too big
            continue
        # pass a subset of the list into recursion
        combos += makeChange(A - coin, coins[i:], cur + [coin])
    return combos

coinset = [1,5,10,25]
A = 10
makeChange(A, coinset)

结果：

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 5]
[5, 5]
[10]
Out[456]:
4

将

A

设置为

200

将显示

1463

组合。