Programare dinamică simplăEdit
O strategie clasică de programare dinamică funcționează în sens ascendent prin găsirea combinațiilor tuturor valorilor mai mici care ar însuma până la pragul curent. Astfel, la fiecare prag, toate pragurile anterioare sunt potențial luate în considerare pentru a lucra în sens ascendent până la suma-țintă W. Din acest motiv, această abordare de programare dinamică necesită un număr de pași care este O(nW), unde n este numărul de tipuri de monede.
ImplementationEdit
Cel de mai jos este o implementare a programării dinamice (cu Python 3) care utilizează o matrice pentru a ține evidența soluțiilor optime ale subproblemelor și returnează numărul minim de monede sau „Infinit” dacă nu există nicio modalitate de a face restul cu monedele date. O a doua matrice poate fi utilizată pentru a obține setul de monede pentru soluția optimă.
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
Programare dinamică cu arborele de convoluție probabilisticăEdit
Arborele de convoluție probabilistică poate fi, de asemenea, utilizat ca o abordare mai eficientă a programării dinamice. Arborele de convoluție probabilistică fuzionează perechi de monede pentru a produce toate sumele care pot fi create de acea pereche de monede (cu niciuna dintre monede prezentă, doar prima monedă prezentă, doar a doua monedă prezentă și ambele monede prezente), iar apoi fuzionează ulterior perechi ale acestor rezultate fuzionate în același mod. Acest proces se repetă până când cele două colecții finale de rezultate sunt fuzionate într-una singură, ceea ce conduce la un arbore binar echilibrat cu W log(W) astfel de operațiuni de fuziune. În plus, prin discretizarea valorilor monedei, fiecare dintre aceste operații de fuziune poate fi efectuată prin convoluție, care poate fi adesea efectuată mai eficient cu ajutorul transformării Fourier rapide (FFT). În acest mod, arborele de convoluție probabilistică poate fi utilizat pentru a obține o soluție într-un număr subcadratic de pași: fiecare convoluție poate fi realizată în n log(n), iar operațiile de fuziune inițiale (mai numeroase) utilizează un n mai mic, în timp ce operațiile ulterioare (mai puțin numeroase) necesită un n de ordinul lui W.
Metoda de programare dinamică bazată pe arborele de convoluție probabilistică rezolvă în mod eficient și generalizarea probabilistică a problemei schimbării, în cazul în care incertitudinea sau neclaritatea sumei țintă W face ca aceasta să fie o distribuție discretă mai degrabă decât o cantitate fixă, în cazul în care valoarea fiecărei monede este, de asemenea, permisă a fi neclară (de exemplu, atunci când se ia în considerare un curs de schimb) și în cazul în care diferite monede pot fi folosite cu anumite frecvențe.
Metoda lacomăEdit
Pentru așa-numitele sisteme de monede canonice, cum sunt cele utilizate în SUA și în multe alte țări, un algoritm lacom de alegere a celei mai mari cupiuri de monede care nu este mai mare decât suma rămasă de realizat va produce rezultatul optim. Acest lucru nu este însă valabil pentru sistemele de monede arbitrare. De exemplu, dacă valoarea nominală a monedelor ar fi 1, 3 și 4, atunci, pentru a face 6, algoritmul lacom ar alege trei monede (4,1,1), în timp ce soluția optimă este de două monede (3,3). Este posibil să se testeze dacă un sistem de monede este canonic (adică dacă algoritmul lacom rezolvă întotdeauna problema schimbării în mod optim) în timp polinomial.
.