需要一個測試用例，其中給出的最小數量的硬幣代碼在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

至於the wikipedia states，該組可能硬幣的貪婪算法將總是返回最佳結果。然而，「如果硬幣面額是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)