Eenvoudige dynamische programmeringEdit
Een klassieke dynamische programmeringsstrategie werkt naar boven toe door de combinaties te vinden van alle kleinere waarden die bij elkaar opgeteld de huidige drempel zouden bereiken. Bij elke drempel worden dus alle vorige drempels in aanmerking genomen om opwaarts te werken naar het doelbedrag W. Daarom vereist deze dynamische programmeringsaanpak een aantal stappen dat O(nW) is, waarbij n het aantal soorten munten is.
ImplementatieEdit
Het volgende is een dynamische programmeerimplementatie (met Python 3) die een matrix gebruikt om de optimale oplossingen voor deelproblemen bij te houden, en het minimum aantal munten teruggeeft, of “Oneindig” als er geen manier is om wisselgeld te maken met de gegeven munten. Een tweede matrix kan worden gebruikt om de verzameling munten voor de optimale oplossing te verkrijgen.
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
Dynamisch programmeren met de probabilistische convolutieboomEdit
De probabilistische convolutieboom kan ook worden gebruikt als een efficiëntere dynamische programmeringsaanpak. De probabilistische convolutieboom voegt paren van munten samen om alle bedragen te produceren die door dat paar munten kunnen worden gecreëerd (met geen van beide munten aanwezig, alleen de eerste munt aanwezig, alleen de tweede munt aanwezig, en beide munten aanwezig), en voegt vervolgens paren van deze samengevoegde uitkomsten op dezelfde manier samen. Dit proces wordt herhaald tot de laatste twee verzamelingen van uitkomsten tot één zijn samengevoegd, wat leidt tot een evenwichtige binaire boom met W log(W) van dergelijke samenvoegingen. Door de muntwaarden te discrimeren kan elk van deze samenvoegingen bovendien worden uitgevoerd via convolutie, die vaak efficiënter kan worden uitgevoerd met de snelle Fouriertransformatie (FFT). Op deze manier kan de probabilistische convolutieboom worden gebruikt om een oplossing te bereiken in een subkwadratisch aantal stappen: elke convolutie kan worden uitgevoerd in n log(n), en de eerste (meer talrijke) samenvoegbewerkingen gebruiken een kleinere n, terwijl de latere (minder talrijke) bewerkingen n in de orde van W vereisen.
De probabilistische convolutieboom-gebaseerde dynamische programmeringsmethode lost ook efficiënt de probabilistische veralgemening van het wisselgeldprobleem op, waar onzekerheid of vaagheid in het doelbedrag W het tot een discrete verdeling maakt in plaats van een vaste hoeveelheid, waar de waarde van elke munt eveneens vaag mag zijn (bijvoorbeeld wanneer een wisselkoers in aanmerking wordt genomen), en waar verschillende munten met bepaalde frequenties kunnen worden gebruikt.
Greedy methodeEdit
Voor de zogenaamde canonieke muntstelsels, zoals die in de VS en vele andere landen worden gebruikt, zal een greedy algoritme waarbij de grootste denominatie van munt wordt gekozen die niet groter is dan het resterende bedrag dat moet worden verdiend, het optimale resultaat opleveren. Dit is echter niet het geval voor willekeurige muntstelsels. Als de muntwaarden bijvoorbeeld 1, 3 en 4 zouden zijn, dan zou het hebzuchtige algoritme om 6 te maken drie munten kiezen (4,1,1), terwijl de optimale oplossing twee munten is (3,3). Het is mogelijk om in polynomiale tijd te testen of een muntstelsel canoniek is (dat wil zeggen, of het greedy-algoritme zijn wisselprobleem altijd optimaal oplost).