Simpel dynamisk programmeringRediger
En klassisk dynamisk programmeringsstrategi fungerer opadrettet ved at finde de kombinationer af alle mindre værdier, der tilsammen svarer til den aktuelle tærskelværdi. Ved hver tærskelværdi tages således alle tidligere tærskelværdier potentielt i betragtning for at arbejde sig opad til målbeløbet W. Af denne grund kræver denne dynamiske programmeringsstrategi et antal trin, der er O(nW), hvor n er antallet af mønttyper.
ImplementationEdit
Det følgende er en implementering af dynamisk programmering (med Python 3), som anvender en matrix til at holde styr på de optimale løsninger på delproblemer og returnerer det mindste antal mønter eller “uendelig”, hvis der ikke er mulighed for at lave byttepenge med de givne mønter. En anden matrix kan bruges til at opnå mængden af mønter for den optimale løsning.
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
Dynamisk programmering med det probabilistiske konvolutionstræRediger
Det probabilistiske konvolutionstræ kan også bruges som en mere effektiv tilgang til dynamisk programmering. Det probabilistiske konvolutionstræ sammensmelter møntpar for at frembringe alle beløb, der kan skabes af det pågældende møntpar (med ingen af mønterne til stede, kun den første mønt til stede, kun den anden mønt til stede og begge mønter til stede), og derefter efterfølgende sammensmelte par af disse sammensmeltede resultater på samme måde. Denne proces gentages, indtil de to sidste samlinger af resultater er slået sammen til ét, hvilket fører til et balanceret binært træ med W log(W) sådanne sammenlægningsoperationer. Ved at diskretisere møntværdierne kan hver af disse sammenlægningsoperationer desuden udføres via konvolution, hvilket ofte kan udføres mere effektivt med den hurtige Fouriertransformation (FFT). På denne måde kan det probabilistiske konvolutionstræ anvendes til at opnå en løsning i et subkvadratisk antal trin: hver konvolution kan udføres på n log(n), og de første (mere talrige) sammenlægningsoperationer bruger et mindre n, mens de senere (mindre talrige) operationer kræver n i størrelsesordenen W.
Den probabilistiske konvolutionstræ-baserede dynamiske programmeringsmetode løser også effektivt den probabilistiske generalisering af problemet med at foretage ændringer, hvor usikkerhed eller fuzziness i målbeløbet W gør det til en diskret fordeling i stedet for en fast størrelse, hvor værdien af hver enkelt mønt ligeledes tillades at være fuzzy (f.eks. når der tages hensyn til en valutakurs), og hvor forskellige mønter kan anvendes med bestemte frekvenser.
Greedy-metodeRediger
For de såkaldte kanoniske møntsystemer, som dem der anvendes i USA og mange andre lande, vil en greedy-algoritme, der består i at vælge den største møntværdi, som ikke er større end det resterende beløb, der skal laves, give det optimale resultat. Dette er dog ikke tilfældet for arbitrære møntsystemer. Hvis møntværdierne f.eks. var 1, 3 og 4, ville den grådige algoritme for at lave 6 mønter vælge tre mønter (4,1,1), mens den optimale løsning er to mønter (3,3). Det er muligt at teste, om et møntsystem er kanonisk (dvs. om den greedy-algoritme altid løser sit problem med at lave byttepenge optimalt) i polynomial tid.