Leave minimal tip

Question

If you need to pay a certain amount of money with different coins, calculating the exact number of coins to pay the amount is simple, you can use something like:

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

This works, if i need to pay 98 $, and I have 50, 10, 5 and 1 coins.

But what if I need to pay 98, but I do not have just 100, 50, 20 coins? (the optimal solution would be to give a 100, and have 2 as loss) Is there a simple platonic way to solve it? Or I need to compute all the different variations, and search for the minimal loss?

Answer 1

@h4z3 Thanks

One solution which works is, if anyone knows a shorter/better version anticipated thanks

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