Оставьте минимальный совет

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 Спасибо

Одно из решений, которое работает, если кто-нибудь знает, что ожидается более короткая / лучшая версия благодаря

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