Enkel dynamisk programmeringRedigera
En klassisk strategi för dynamisk programmering fungerar uppåt genom att hitta kombinationer av alla mindre värden som sammanlagt skulle uppgå till det aktuella tröskelvärdet. Vid varje tröskelvärde beaktas således potentiellt alla tidigare tröskelvärden för att arbeta uppåt till målbeloppet W. Av denna anledning kräver denna strategi för dynamisk programmering ett antal steg som är O(nW), där n är antalet mynttyper.
ImplementationEdit
Nedan följer en implementering av dynamisk programmering (med Python 3) som använder en matris för att hålla reda på de optimala lösningarna på delproblemen och som returnerar det minsta antalet mynt eller ”oändligt” om det inte går att göra växel med de givna mynten. En andra matris kan användas för att få fram mängden mynt för den optimala lösningen.
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 probabilistiska konvolutionsträdetRedigera
Det probabilistiska konvolutionsträdet kan också användas som en effektivare metod för dynamisk programmering. Det probabilistiska konvolutionsträdet slår ihop par av mynt för att producera alla belopp som kan skapas av det paret av mynt (med inget av mynten närvarande, endast det första myntet närvarande, endast det andra myntet närvarande och båda mynten närvarande), och sedan därefter slå ihop par av dessa sammanslagna resultat på samma sätt. Denna process upprepas tills de två sista samlingarna av resultat har slagits samman till ett, vilket leder till ett balanserat binärt träd med W log(W) sådana sammanslagningsoperationer. Genom att diskretisera myntvärdena kan dessutom var och en av dessa sammanslagningsoperationer utföras via konvolution, vilket ofta kan utföras mer effektivt med den snabba Fouriertransformen (FFT). På detta sätt kan det probabilistiska konvolutionsträdet användas för att uppnå en lösning i ett subkvadratiskt antal steg: varje konvolution kan utföras på n log(n), och de inledande (fler) sammanslagningarna använder ett mindre n, medan de senare (färre) operationerna kräver n i storleksordningen W.
Den probabilistiska konvolutionsträdsbaserade dynamiska programmeringsmetoden löser också effektivt den probabilistiska generaliseringen av växlingsproblemet, där osäkerhet eller luddighet i målbeloppet W gör det till en diskret fördelning i stället för en fast kvantitet, där värdet av varje mynt likaså tillåts vara luddigt (t.ex. när man beaktar en växelkurs), och där olika mynt kan användas med särskilda frekvenser.
Greedy-metodEdit
För de så kallade kanoniska myntsystemen, som de som används i USA och många andra länder, ger en greedy-algoritm som går ut på att välja det största myntvärdet som inte är större än den återstående summan som ska göras det optimala resultatet. Detta gäller dock inte för godtyckliga myntsystem. Om myntvalörerna till exempel är 1, 3 och 4 skulle den giriga algoritmen välja tre mynt (4,1,1) för att göra 6 mynt, medan den optimala lösningen är två mynt (3,3). Det är möjligt att testa om ett myntsystem är kanoniskt (det vill säga om den giriga algoritmen alltid löser växlingsproblemet optimalt) på polynomial tid.