Programmazione dinamica sempliceModifica
Una strategia classica di programmazione dinamica lavora verso l’alto trovando le combinazioni di tutti i valori più piccoli che sommano alla soglia corrente. Così, ad ogni soglia, tutte le soglie precedenti sono potenzialmente considerate per lavorare verso l’alto fino all’importo obiettivo W. Per questo motivo, questo approccio di programmazione dinamica richiede un numero di passi che è O(nW), dove n è il numero di tipi di monete.
ImplementazioneModifica
Quella che segue è un’implementazione di programmazione dinamica (con Python 3) che utilizza una matrice per tenere traccia delle soluzioni ottimali dei sottoproblemi, e restituisce il numero minimo di monete, o “Infinito” se non c’è modo di fare il resto con le monete date. Una seconda matrice può essere usata per ottenere l’insieme di monete per la soluzione ottimale.
def _get_change_making_matrix(set_of_coins, r: int): m = for _ in range(len(set_of_coins) + 1)] for i in range(1, r + 1): m = float('inf') # By default there is no way of making change return mdef change_making(coins, n: int): """This function assumes that all coins are available infinitely. n is the number to obtain with the fewest coins. coins is a list or tuple with the available denominations. """ m = _get_change_making_matrix(coins, n) for c in range(1, len(coins) + 1): for r in range(1, n + 1): # Just use the coin coins. if coins == r: m = 1 # coins cannot be included. # Use the previous solution for making r, # excluding coins. elif coins > r: m = m # coins can be used. # Decide which one of the following solutions is the best: # 1. Using the previous solution for making r (without using coins). # 2. Using the previous solution for making r - coins (without # using coins) plus this 1 extra coin. else: m = min(m, 1 + m]) return m
Programmazione dinamica con l’albero di convoluzione probabilisticoModifica
L’albero di convoluzione probabilistico può anche essere usato come approccio di programmazione dinamica più efficiente. L’albero di convoluzione probabilistica fonde coppie di monete per produrre tutti gli importi che possono essere creati da quella coppia di monete (con nessuna moneta presente, solo la prima moneta presente, solo la seconda moneta presente, ed entrambe le monete presenti), e poi successivamente fondendo coppie di questi risultati fusi nello stesso modo. Questo processo viene ripetuto fino a quando le due collezioni finali di risultati vengono fuse in una sola, portando ad un albero binario bilanciato con W log(W) tali operazioni di fusione. Inoltre, discretizzando i valori delle monete, ognuna di queste operazioni di fusione può essere eseguita tramite convoluzione, che spesso può essere eseguita in modo più efficiente con la trasformata veloce di Fourier (FFT). In questo modo, l’albero di convoluzione probabilistico può essere utilizzato per ottenere una soluzione in un numero sub-quadratico di passi: ogni convoluzione può essere eseguita in n log(n), e le operazioni di fusione iniziali (più numerose) utilizzano un n più piccolo, mentre le operazioni successive (meno numerose) richiedono n dell’ordine di W.
Il metodo di programmazione dinamica basato sulla convoluzione probabilistica ad albero risolve in modo efficiente anche la generalizzazione probabilistica del problema del cambio, dove l’incertezza o la fuzziness nell’ammontare dell’obiettivo W lo rende una distribuzione discreta piuttosto che una quantità fissa, dove il valore di ogni moneta è anche permesso essere fuzzy (per esempio, quando si considera un tasso di cambio), e dove monete diverse possono essere usate con frequenze particolari.
Metodo greedyModifica
Per i cosiddetti sistemi di monete canoniche, come quelli usati negli Stati Uniti e in molti altri paesi, un algoritmo greedy di scegliere il più grande taglio di moneta che non sia maggiore della quantità rimanente da fare produrrà il risultato ottimale. Questo non è però il caso di sistemi di monete arbitrari. Per esempio, se i tagli delle monete fossero 1, 3 e 4, allora per fare 6, l’algoritmo avido sceglierebbe tre monete (4,1,1) mentre la soluzione ottimale è due monete (3,3). È possibile verificare se un sistema di monete è canonico (cioè se l’algoritmo greedy risolve sempre il suo problema di cambio in modo ottimale) in tempo polinomiale.