Proste programowanie dynamiczneEdit
Klasyczna strategia programowania dynamicznego działa w górę poprzez znalezienie kombinacji wszystkich mniejszych wartości, które sumują się do bieżącego progu. Tak więc, przy każdym progu, wszystkie poprzednie progi są potencjalnie brane pod uwagę, aby pracować w górę do kwoty docelowej W. Z tego powodu, to podejście programowania dynamicznego wymaga liczby kroków, która jest O(nW), gdzie n jest liczbą typów monet.
ImplementacjaEdit
Poniżej znajduje się implementacja programowania dynamicznego (z Pythonem 3), która używa macierzy do śledzenia optymalnych rozwiązań podproblemów i zwraca minimalną liczbę monet lub „nieskończoność”, jeśli nie ma sposobu, aby dokonać zmiany za pomocą podanych monet. Druga macierz może być użyta do uzyskania zestawu monet dla optymalnego rozwiązania.
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
Programowanie dynamiczne z probabilistycznym drzewem konwolucjiEdit
Drzewo konwolucji probabilistycznej może być również użyte jako bardziej efektywne podejście do programowania dynamicznego. Drzewo konwolucji probabilistycznej łączy pary monet, aby uzyskać wszystkie kwoty, które mogą być utworzone przez tę parę monet (przy braku monety, tylko pierwsza moneta jest obecna, tylko druga moneta jest obecna i obie monety są obecne), a następnie łączy pary tych połączonych wyników w ten sam sposób. Proces ten jest powtarzany aż do końcowych dwóch kolekcji wyników są łączone w jeden, co prowadzi do zrównoważonego drzewa binarnego z W log(W) takich operacji łączenia. Ponadto, poprzez dyskretyzację wartości monet, każda z tych operacji łączenia może być wykonana poprzez konwolucję, która często może być wykonana bardziej efektywnie za pomocą szybkiej transformaty Fouriera (FFT). W ten sposób, probabilistyczne drzewo konwolucji może być użyte do osiągnięcia rozwiązania w podkwadratowej liczbie kroków: każda konwolucja może być wykonana w n log(n), a początkowe (liczniejsze) operacje łączenia używają mniejszego n, podczas gdy późniejsze (mniej liczne) operacje wymagają n rzędu W.
Metoda programowania dynamicznego oparta na probabilistycznym drzewie konwolucji również skutecznie rozwiązuje probabilistyczne uogólnienie problemu wydawania reszty, gdzie niepewność lub rozmytość w kwocie celu W czyni ją dyskretnym rozkładem, a nie stałą wielkością, gdzie wartość każdej monety jest również dozwolona jako rozmyta (na przykład, gdy rozważany jest kurs wymiany), i gdzie różne monety mogą być używane z określoną częstotliwością.
Metoda chciwościEdit
Dla tak zwanych kanonicznych systemów monet, takich jak te używane w USA i wielu innych krajach, chciwy algorytm wybierania największego nominału monety, który nie jest większy niż pozostała kwota do zrobienia da optymalny wynik. Nie jest tak jednak w przypadku dowolnych systemów monetarnych. Na przykład, jeśli nominały monet to 1, 3 i 4, to aby wykonać 6, chciwy algorytm wybrałby trzy monety (4,1,1), podczas gdy optymalnym rozwiązaniem są dwie monety (3,3). Możliwe jest sprawdzenie, czy system monet jest kanoniczny (to znaczy, czy algorytm zachłanny zawsze rozwiązuje problem wydawania reszty optymalnie) w czasie wielomianowym.