Yksinkertainen dynaaminen ohjelmointiEdit
Klassinen dynaamisen ohjelmoinnin strategia toimii ylöspäin etsimällä kaikkien sellaisten pienempien arvojen yhdistelmiä, joiden summa on nykyisen kynnysarvon suuruinen. Näin ollen jokaisen kynnysarvon kohdalla kaikki aiemmat kynnysarvot otetaan mahdollisesti huomioon, jotta voidaan työskennellä ylöspäin tavoitesummaan W. Tästä syystä tämä dynaamisen ohjelmoinnin lähestymistapa vaatii askelten määrän, joka on O(nW), missä n on kolikkotyyppien lukumäärä.
ToteutusEdit
Seuraavassa on dynaamisen ohjelmoinnin toteutus (Python 3:lla), joka käyttää matriisia pitääkseen kirjaa osaongelmien optimaalisista ratkaisuista ja palauttaa pienimmän kolikkomäärän tai ”Äärettömän”, jos annetuilla kolikoilla ei voi tehdä vaihtorahaa. Toista matriisia voidaan käyttää optimaalisen ratkaisun kolikkojoukon saamiseksi.
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
Dynaaminen ohjelmointi probabilistisella konvoluutiopuullaMuutos
Todennäköistä konvoluutiopuuta voidaan käyttää myös tehokkaampana dynaamisen ohjelmoinnin lähestymistapana. Todennäköisyyteen perustuva konvoluutiopuu sulauttaa kolikkopareja siten, että saadaan kaikki määrät, jotka voidaan luoda kyseisellä kolikkoparilla (kun kumpikaan kolikko ei ole läsnä, vain ensimmäinen kolikko on läsnä, vain toinen kolikko on läsnä ja molemmat kolikot ovat läsnä), ja sen jälkeen sulautetaan näiden sulautettujen lopputulosten pareja samalla tavalla. Tätä prosessia toistetaan, kunnes kaksi viimeistä tuloskokoelmaa on yhdistetty yhdeksi, mikä johtaa tasapainoiseen binääripuuhun, jossa on W log(W) tällaista yhdistämisoperaatiota. Kun kolikon arvot diskretoidaan, jokainen näistä yhdistämisoperaatioista voidaan suorittaa konvoluution avulla, mikä voidaan usein suorittaa tehokkaammin nopealla Fourier-muunnoksella (FFT). Tällä tavoin todennäköisyysperusteista konvoluutiopuuta voidaan käyttää ratkaisun saavuttamiseen alle kvartaalisessa määrässä vaiheita: kukin konvoluutio voidaan suorittaa n log(n):ssä, ja ensimmäiset (useammat) yhdistämisoperaatiot käyttävät pienempää n:ää, kun taas myöhemmät (harvemmat) operaatiot vaativat n:n W:n luokkaa.
Todennäköisyyspohjaiseen konvoluutiopuuhun perustuva dynaamisen ohjelmoinnin menetelmä ratkaisee tehokkaasti myös vaihdon tekemisen ongelman todennäköisyyspohjaisen yleistyksen, jossa epävarmuus tai epäselvyys tavoitesummassa W tekee siitä diskreetin jakauman kiinteän suureen sijaan, jossa kunkin kolikon arvo saa niin ikään olla epäselvä (esimerkiksi kun otetaan huomioon vaihtokurssi) ja jossa eri kolikoita saatetaan käyttää tietyllä tiheydellä.
Ahne menetelmäMuokkaa
Ns. kanonisissa kolikkojärjestelmissä, kuten Yhdysvalloissa ja monissa muissa maissa käytetyissä, optimaalisen tuloksen tuottaa ahne algoritmi, jossa valitaan suurin nimellisarvoinen kolikko, joka ei ole suurempi kuin jäljelle jäävä valmistettava määrä. Näin ei kuitenkaan ole mielivaltaisissa kolikkojärjestelmissä. Jos esimerkiksi kolikoiden nimellisarvot olisivat 1, 3 ja 4, ahne algoritmi valitsisi kolme kolikkoa (4,1,1), kun taas optimaalinen ratkaisu on kaksi kolikkoa (3,3), jos halutaan tehdä 6 kolikkoa. On mahdollista testata polynomiajassa, onko kolikkojärjestelmä kanoninen (eli ratkaiseeko ahne algoritmi sen vaihtorahojen teko-ongelman aina optimaalisesti).