Il problema del resto
Un cassiere che dà il resto prende la moneta più grande che ci sta, poi la successiva, e con euro o dollari questo dà sempre il minimo di monete. Se però le monete sono 1, 3 e 4, la stessa abitudine paga 6 con tre monete quando ne basterebbero due. La programmazione dinamica trova il vero minimo per qualsiasi insieme di monete.
Due domande
Il problema del resto si presenta in due varianti. La prima chiede il minimo di monete che formano un importo esatto; è nota anche come problema del cambio. La seconda chiede quante combinazioni diverse di monete lo formano. In entrambe ogni tipo di moneta si può usare tutte le volte che si vuole, ed entrambe si risolvono costruendo la risposta per ogni importo a partire dalle risposte per gli importi più piccoli.
Minimo di monete, passo dopo passo
Crea una fila di celle per gli importi da 0 fino all'obiettivo. L'importo 0 richiede 0 monete; ogni altro importo parte da infinito. Scorri gli importi in ordine e per ciascuno prova ogni moneta c che ci sta: la cella dell'importo meno c, più una moneta, è un candidato. Tieni il più piccolo. Ogni cella dipende solo da celle alla sua sinistra, che sono già definitive, quindi una sola passata riempie la fila.
Un esempio
Con le monete 1, 3 e 4: l'importo 1 richiede 1 moneta, 2 ne richiede 2, 3 ne richiede 1 (una sola moneta da 3) e 4 ne richiede 1. Per 5 si prova 1 (4 richiede 1, quindi 2 monete), 3 (2 richiede 2, quindi 3 monete) e 4 (1 richiede 1, quindi 2 monete): il migliore è 2. Per 6 si prova 1 (5 richiede 2, quindi 3), 3 (3 richiede 1, quindi 2) e 4 (2 richiede 2, quindi 3): il migliore è 2, con 3 + 3. Il greedy avrebbe pagato 4 + 1 + 1.
Contare i modi
Per contare le combinazioni, aggiungi le monete una alla volta. Con la sola prima moneta, ogni importo si forma in un solo modo oppure non si forma affatto. Quando arriva una nuova moneta c, i modi per formare un importo a sono i vecchi modi, senza c, più i modi per formare a − c con c di nuovo ammessa, perché ognuno di questi diventa un modo per formare a aggiungendo un'altra c. Con le monete 1, 2 e 5 ci sono 4 modi per formare 5: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 e 1 + 1 + 1 + 1 + 1.
Quando il greedy basta
Un sistema di monete per cui il greedy dà sempre il minimo di monete si dice canonico. La maggior parte delle valute moderne è progettata così, e nel 1994 David Pearson descrisse un test che verifica un sistema di monete in un numero di passi che cresce solo in modo polinomiale con il numero di monete. Le vecchie monete britanniche non erano canoniche: il greedy paga 48 pence con una mezza corona, uno scellino e un sixpence, quando basterebbero due fiorini.
Esploralo
Apri l'app, passa alla vista Tabella e premi Passo. Nella modalità Minimo di monete, la cella arancione è l'importo in calcolo e la cella blu è l'importo più piccolo che la moneta lascia; la riga sotto conserva l'ultima moneta, e alla fine le monete si rileggono lungo di essa. Passa a Numero di modi e guarda i conteggi crescere riga dopo riga man mano che si aggiunge ogni moneta.
Domande frequenti
Il problema del resto è un problema dello zaino?
Un parente stretto. La variante del minimo di monete è un problema dello zaino illimitato in cui ogni moneta è un oggetto il cui peso è il suo valore nominale, lo zaino va riempito esattamente e l'obiettivo è usare il minor numero di oggetti.
Qual è la complessità temporale?
O(k·A) per k tipi di monete e un importo A, in entrambe le varianti. La tabella del minimo di monete ha A + 1 celle e quella dei modi (k + 1)·(A + 1), anche se basta una sola riga se le celle vengono aggiornate sul posto.
Perché contare le monete in un ordine fisso?
Se ogni importo provasse ogni moneta, 1 + 2 e 2 + 1 verrebbero contati come due modi. Aggiungere le monete una riga alla volta significa che una combinazione viene sempre costruita prima con le monete precedenti, così ognuna viene contata esattamente una volta.
Si possono rileggere le monete anche per il numero di modi?
Non come un'unica risposta, perché ce ne sono molte. La variante del minimo di monete conserva l'ultima moneta di ogni importo, e questo basta per ricostruire una combinazione ottimale.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova il problema del resto