muutosongelma käsittelee kysymystä tietyn rahamäärän yhteenlaskevien (tietynlaisten) kolikoiden vähimmäismäärän löytämisestä. Se on erikoistapaus kokonaisluku knapsack ongelma, ja on sovelluksia laajempi kuin vain valuutta.
se on myös yleisin kolikoiden muutosongelman muunnelma, yleinen jakotapaus, jossa äärettömän kolikkosarjan käytettävissä olevat nimellisarvot huomioon ottaen pyritään selvittämään, kuinka monta mahdollista tapaa tehdä muutos tiettyyn rahamäärään, ottamatta huomioon kolikoiden järjestystä.
muutoksen tekeminen on minimointiongelma, valitsemme ratkaisun, jossa meidän on annettava vähimmäismäärä kolikoita tietylle määrälle.
- ahne menetelmä
2. Dynaaminen menetelmä
dynaaminen ohjelmointi
klassinen dynaaminen ohjelmointistrategia toimii ylöspäin löytämällä kaikkien pienempien arvojen yhdistelmät, jotka summautuvat nykyiseen kynnysarvoon.Näin ollen kaikkien aikaisempien kynnysarvojen voidaan katsoa työntyvän ylöspäin tavoitesummaan W. tästä syystä tämä dynaaminen ohjelmointitapa saattaa vaatia useita vaiheita, jotka ovat vähintään nelikulmaisia tavoitesummassa W.
optimaalinen kolikkomuutos olemme nähneet tämän, haluat tehdä muutoksen käyttäen nimellisarvojärjestelmää mahdollisimman pienellä määrällä kolikoita. Joskus ahne algoritmi antaa optimaalisen ratkaisun. Mutta joskus se ei-esimerkki oli järjestelmä (12, 5, 1), jossa dynaaminen algoritmi antaa 15 = 12 + 1 + 1 + 1 mutta parempi vastaus on 15 = 5 + 5 + 5. dynamic antaa kuitenkin aina optimaalisen ratkaisun tai mahdolliset minimirahat nimittäjien sisällä.
vaiheet:-
löydämme minimin no. kolikoita tarvitaan määrä .
summa on se summa, jonka osalta olemme tekemässä muutosta.
ensin asetetaan min. Ei. vaadituista kolikoista ts., min = INFINITY
tämä tarkoittaa, ettemme aluksi tiedä, kuinka monta kolikkoa tarvitaan.
sitten Tarkistamme jokaisen nimellisarvoisen kolikon ja katsomme, voiko sillä saada ratkaisun.
Jos se on mahdollista, päivitämme min-ja kolikkomuuttujat.
missä, min = minimi no. kolikoista, joita tarvitaan muutoksen tekemiseen määrän mukaan
coin = kolikon ensimmäinen indeksi ratkaisussa
esimerkki:
Amount = 5
coins = {1,2,3}
Ways to make change = 5
