a változtatási probléma azzal a kérdéssel foglalkozik, hogy megtalálják-e az adott pénzösszeghez tartozó (bizonyos címletű) érmék minimális számát. Ez az egész hátizsák probléma speciális esete, és alkalmazásai szélesebbek, mint a pénznem.
Ez az érmeváltási probléma leggyakoribb változata is, a partíció általános esete, amelyben a végtelen érmekészlet rendelkezésre álló címletei miatt a cél az, hogy megtudja, hány lehetséges módja van egy adott pénzösszeg megváltoztatásának, anélkül, hogy figyelembe venné az érmék sorrendjét.
a változtatás minimalizálási probléma, azt a megoldást választjuk, ahol az adott összeghez minimális számú érmét kell adnunk.
- kapzsi módszer
2. Dinamikus módszer
dinamikus programozás
a klasszikus dinamikus programozási stratégia felfelé működik azáltal, hogy megtalálja az összes kisebb érték kombinációját, amelyek összegeznék az aktuális küszöbértéket.Így minden küszöbértéknél az összes korábbi küszöbérték potenciálisan úgy tekinthető, hogy felfelé működik a célösszegig W. emiatt ez a dinamikus programozási megközelítés számos lépést igényelhet, amelyek legalább kvadratikusak a célösszegben W.
optimális érmeváltás láttuk ezt, változtatni szeretne egy címletrendszer segítségével, a lehető legkevesebb érme felhasználásával. Néha a mohó algoritmus adja az optimális megoldást. De néha nem – példa volt a rendszer (12, 5, 1), ahol a dinamikus algoritmus 15 = 12 + 1 + 1 + 1 de a jobb válasz 15 = 5 + 5 + 5. de a dinamikus mindig optimális megoldást vagy lehetséges minimális érméket ad a nevezőkön belül.
lépések:-
megtaláljuk a minimális számot. az összeghez szükséges érmék .
Az összeg az az összeg, amelyre a változtatást elvégezzük.
először min. Nem. szükséges érmék, pl., min = INFINITY
Ez azt jelenti, hogy kezdetben nem tudjuk, hány érmére lesz szükség.
ezután ellenőrizzük az egyes címletű érméket, és megnézzük, hogy fel lehet-e használni a megoldást.
ha lehetséges, akkor frissítjük a min és coin változókat.
ahol, min = minimum nem. érme = első index az érme a megoldás
példa:
összeg = 5
érmék = {1,2,3}
módon, hogy a változás = 5
