Algoritmo di cambio monete

Question

Supponiamo di avere un set di monete con denominazioni a1, a2, ... ak.

Uno di loro è noto per essere uguale a 1.

voglio fare il cambiamento per tutti gli interi da 1 a n utilizzando il numero minimo di monete.

Qualsiasi idea per l'algoritmo.

eg. 1, 3, 4 coin denominations 
n = 11 
optimal selection is 3, 0, 2 in the order of coin denominations. 

n = 12 
optimal selection is 2, 2, 1. 

Nota: non compiti a casa solo una modifica del this problema

Answer 1

Questo è un classico problema di programmazione dinamica (si noti prima che l'algoritmo greedy non funziona sempre qui!).

Assumere le monete sono ordinate in modo che a_1 > a_2 > ... > a_k = 1. Definiamo un nuovo problema. Diciamo che il problema (i, j) consiste nel trovare il numero minimo di monete che apportano modifiche per j utilizzando monete a_i > a_(i + 1) > ... > a_k. Il problema che vogliamo risolvere è (1, j) per qualsiasi j con 1 <= j <= n. Supponi che C(i, j) sia la risposta al problema (i, j).

Ora, considerare un'istanza (i, j). Dobbiamo decidere se stiamo usando o meno una delle monete a_i. Se non lo siamo, stiamo solo risolvendo un problema (i + 1, j) e la risposta è C(i + 1, j). Se lo siamo, completiamo la soluzione apportando modifiche per j - a_i. Per fare ciò usando il minor numero possibile di monete, vogliamo risolvere il problema (i, j - a_i). Organizziamo le cose in modo che questi due problemi sono già risolti per noi e poi:

C(i, j) = C(i + 1, j)       if a_i > j 
     = min(C(i + 1, j), 1 + C(i, j - a_i)) if a_i <= j 

ora capire che cosa i primi casi sono e come tradurre questo per la lingua di vostra scelta e si dovrebbe essere a posto.

Se si desidera provare le mani a un altro problema interessante che richiede una programmazione dinamica, consultare Project Euler Problem 67.

Answer 2

Ecco un'implementazione di esempio di un algoritmo di programmazione dinamica in Python. È più semplice dell'algoritmo descritto da Jason, perché calcola solo 1 riga della tabella 2D che descrive.

Si prega di notare che l'uso di questo codice per imbrogliare i compiti farà piangere Zombie Dijkstra.

import sys 
def get_best_coins(coins, target): 
    costs = [0] 
    coins_used = [None] 
    for i in range(1,target + 1): 
     if i % 1000 == 0: 
      print '...', 
     bestCost = sys.maxint 
     bestCoin = -1 
     for coin in coins: 
      if coin <= i: 
       cost = 1 + costs[i - coin] 
       if cost < bestCost: 
        bestCost = cost 
        bestCoin = coin 
     costs.append(bestCost) 
     coins_used.append(bestCoin) 
    ret = []  
    while target > 0: 
     ret.append(coins_used[target]) 
     target -= coins_used[target] 
    return ret 

coins = [1,10,25] 
target = 100033 
print get_best_coins(coins, target)