分而治之-最小硬币数-将硬币作为阵列返回

Question

下面是最小硬币变化问题的蛮力解决方案。它需要一个int更改，也就是需要进行的更改，以及一系列硬币面值。它返回进行更改所需的最低硬币。

我如何修改它以同时返回一组硬币？

例如，如果要求给出值为[1,2,5]的10美分的零钱，它应该返回2个硬币分钟和一个数组[0,0,2]的2个硬币。

def recMC(coinValueList,change):
    minCoins = change
    if change in coinValueList:
        return 1
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList,change-i)
        if numCoins < minCoins:
            minCoins = numCoins
     return minCoins

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

Answer 1

与任何递归函数一样，您从保护条件开始—该测试告诉您何时完成：

if change in coinValueList:
    return 1

要将其转换为硬币列表，只需返回由1个硬币组成的列表：

if change in coinValueList:
    return [ change ]   

在函数的另一部分，您知道递归调用将返回一个列表。因此，只需将列表扩大：

        numCoins = 1 + recMC(coinValueList,change-i)

变成：

        coins = [ i ] + recMC(coinValueList, change - i)

您还必须更新其他测试。