需要一个测试用例，其中给定的最小硬币数量的代码在 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)