python - 需要一个测试用例，其中给定的最少硬币数量的代码在 python 中失败？

Question

下面是计算给定金额找零的代码： 然而，它并没有给出找零数量的最小硬币数量，但代码似乎给出了所需的最小硬币数量。我想要一个案例，它不能提供所需的最少硬币。

def change(amount):
    money = ()
    for coin in [25,10,5,1]:
        num = amount/coin
        money += (coin,) * num
        amount -= coin * num

    return money

print change(59)

output is: 
(25, 25, 5, 1, 1, 1, 1)

Answer 1

正如维基百科所述，对于那组可能的硬币，贪心算法将始终返回最佳结果。但是，“[...] 如果硬币面额是 1、3 和 4，那么要制作 6，贪心算法会选择三个硬币 (4,1,1)，而最优解是两个硬币 (3,3) ”。

因此，您需要更改可能的硬币集以面对该算法的非最佳解决方案。

Answer 2

如前所述，贪心解决方案适用于该组硬币。

适用于所有硬币集的最佳算法示例：

coins = (1, 5, 10, 25)

def change(amount):
    min_coins = [()]
    for i in range(1, amount+1):
        best = min((min_coins[i-x] + (x,) for x in coins if i >= x), key=len)
        min_coins.append(best)
    return min_coins[amount]

print change(59)

Answer 3

从字面上看测试用例的期望结果，负数可能导致它无法提供所需的最小硬币数量。

print change(-1)
(10, 10, 1, 1, 1, 1)