Coin change
💡
Il problema del coin change è uno dei più noti problemi di Dynamic Programming. Mostra in modo chiaro il contrasto tra l’approccio Greedy e quello dinamico, evidenziando come si possa facilmente cadere nell’errore di pensare che l’algoritmo Greedy sia sufficiente. In realtà, quest’ultimo fornisce solo una soluzione subottimale, senza risolvere il problema in senso globale.
Dato un sistema monetario composto da
n monete, ognuna con un valore positivo , si richiede di ottenere una somma totale x utilizzando il minor numero possibile di monete.Per esempio, se i valori delle monete sono e vogliamo ottenere
11, la scelta ottimale sarebbe 1 + 5 + 5 ⇒ 3 monete.Input
La prima riga dell’input contiene due interi
n (1 ≤ n ≤ 100) e x (1 ≤ x ≤ ).La riga successiva contiene
n interi separati da spazio (1 ≤ ≤ ).Output
Il programma deve stampare il numero minimo di monete necessario per ottenere
x. Se non è possibile formare la somma desiderata, il programma deve stampare -1.Esempi
Ingresso | Uscita |
3 11
1 5 7 | 3 |
3 12
1 5 7 | 2 |
Spiegazione
- 11 → 1 + 5 + 5
- 12 → 5 + 7
Tutorial
Notate che la strategia Greedy, cioè prendere sempre la moneta più grande possibile, non funziona. Il primo esempio lo mostra chiaramente. Se vogliamo ottenere 11 e prendiamo prima la moneta da 7, ci resta 4 da formare, per cui servono quattro monete da 1, arrivando a 5 monete totali. La vera soluzione, invece, ne richiede solo 3 (5 + 5 + 1).
Definiamo uno stato
d[i], che rappresenta il numero minimo di monete richiesto per formare la somma i. Se inizializziamo e aggiorniamo correttamente il vettore d fino a x, la risposta definitiva sarà proprio d[x].All’inizio possiamo impostare tutti i valori di
d a infinito (che significa “non è possibile formare tale somma”) eccetto d[0], che è 0 (ottenibile con 0 monete):c = [...]
x = ...
d = [0] + [float('inf')] * x # d[0] è 0 e d[1...x] è inizialmente infinitoPoi, per ogni valore da
1 a x, proviamo a determinare il numero minimo di monete necessario per ottenerlo. Se stiamo considerando un certo valore num, testiamo tutte le monete possibili per vedere se possiamo arrivare a num sommando il valore della moneta a uno stato già noto (num - ). Se migliora (ossia riduce) la quantità di monete necessarie, aggiorniamo d[num]. Quindi, per ogni num da 1 a x, valutiamo tutti i precedenti stati possibili e proviamo a migliorare d[num]:for num in range(1, x + 1): # Itera su tutti i numeri da 1 a x
for ci in c: # Tenta di migliorare d[num] con tutte le monete
if num - ci >= 0: # Se è possibile ottenere num con la moneta ci
d[num] = min(d[num], d[num - ci] + 1)
print(d[x])d[num] = min(d[num], d[num - ci] + 1) è il centro della soluzione. A ogni iterazione cerchiamo di migliorare d[num] se è possibile farlo via num - . In sostanza, prendiamo il numero minimo di monete necessario per formare num - e aggiungiamo 1 per usare la moneta .Al termine dell’elaborazione di tutti i numeri con tutte le monete, la risposta è semplicemente il valore di
d[x].Simuliamo l’algoritmo sull’esempio:
c = [1, 5, 7] e x = 11
d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
num = 1(cerchiamo di migliorare il numero di monete per la somma 1)
num = 2(cerchiamo di migliorare il numero di monete per la somma 2)
num = 3(cerchiamo di migliorare il numero di monete per la somma 3)
num = 4(cerchiamo di migliorare il numero di monete per la somma 4)
num = 5(cerchiamo di migliorare il numero di monete per la somma 5)
num = 6(cerchiamo di migliorare il numero di monete per la somma 6)
num = 7(cerchiamo di migliorare il numero di monete per la somma 7)
num = 8(cerchiamo di migliorare il numero di monete per la somma 8)
num = 9(cerchiamo di migliorare il numero di monete per la somma 9)
num = 10(cerchiamo di migliorare il numero di monete per la somma 10)
num = 11(cerchiamo di migliorare il numero di monete per la somma 11)
print(d[11])⇒ stampa 3
Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB