留下最少的小费

Question

如果你需要用不同的硬币支付一定数量的钱，计算支付金额的确切硬币数量很简单，你可以使用这样的东西：

for i, j in zip(coins, needed): 
         if amount >= 2*i: 
             j = amount // i 
             amount = amount - j * i 
             print (i ," : ", j)

这有效，如果我需要支付 98 美元，并且我有 50、10、5 和 1 个硬币。

但如果我需要支付 98，但我没有 100、50、20 个硬币怎么办？（最佳解决方案是给 100，损失 2）有没有一种简单的柏拉图式的方法来解决它？或者我需要计算所有不同的变化，并搜索最小损失？

Answer 1

@h4z3 谢谢

一个有效的解决方案是，如果有人知道预期的 shorter/better 版本，谢谢

d_amount = amount
x=0
while True:
    served_coins = []
    served_units = []
    for i, j in zip(coins, needed): 
         if d_amount >= i: 
             j = d_amount // i 
             d_amount = d_amount - j * i 
             served_coins.append(i)
             served_units.append(j)
    #print d_amount
    if (d_amount == 0):
        break
    else:
        x = x + 1
    d_amount = amount + x

留下最少的小费

Leave minimal tip

python

optimization

loss