1. megoldás - rekurzióval
A megoldáshoz egy olyan függvényt (programot) kell írnunk, ami egy S összsúlyhoz és egy pénzérme-listához megadja a lehető legkisebb lehetséges összértéket. Nevezzük el ezt a függvényt MinErtek(S)-nek. Legyen a visszatérési értéke a minimális összérték, S paramétere az összsúly, az érme-listát pedig adottnak tekinti, és globális változókon keresztül veszi át. Pl.: N féle pénzérme létezik, az i-edik pénzérme súlya suly[i], értéke pedig ertek[i]!
A MinErtek(S) függvény könnyen megtervezhető rekurzívan.
Tegyük fel, hogy a MinErtek() függvény már helyes minimumot ad minden S0 < S paraméterre,
Tekintsünk egy kiválasztott pénzérmét, és próbálgassuk végig az összes lehetséges pénzérme-típust a helyére. Amikor az i-edik típust próbáljuk, akkor a minimális értéknek ertek[i] + MinErtek(S - suly[i]) adódik. Meg kell keresni azt az i-t, amire ez a becslés legkisebb lesz, és az a becslés lesz a megoldás. (Tudjuk, hogy MinErtek(0) = 0, és ebből teljes indukcióval adódik, hogy minden nagyobb súlyra is pontos a becslés. Ugyanis MinErtek(S) kiszámításához csak a MinErtek(0), MinErtek(1), ... MinErtek(S-1) értkékek kellhetnek.)
MinErtek(S):
Ha S <= 0 Akkor MinErtek := 0
Különben
min_ertek:= -1;
Ciklus i := 1-től N-ig
S0 := S-suly[i];
Ha S0 >= 0 Akkor
ertek0 := MinErtek(S0) + ertek[i];
Ha (ertek0 < min_ertek) vagy
(min_ertek = -1) Akkor
min_ertek := ertek0;
Elágazás vége
Elágazás vége
Ciklus vége
MinErtek := min_ertek;
Elágazás vége
Eljárás vége
A ciklus egy minimum-kiválasztással meghatározza az S össztömegű pénzérmekupac minimális lehetséges értékét. Mindezt úgy teszi, hogy végigpróbálgatja az összes lehetséges pénzérmét a kupac egy kiválasztott érméjére, és a kupac fennmaradó részének min. értékét a MinErtek(S0) függvénnyel, tehát önmagával, rekurzív módon becsli. Pl. ha a kiválasztott érme i-edik típusú, akkor a kupac minimális értékének a következőt kapjuk: MinErtek(S-suly[i])+ertek[i]. Ez az algoritmus:
- Véges időn belül le fog futni, mert mindig csökkenő paraméterekkel hívja meg a függvény önmagát.
- Végignézi a perselyben lévő összes lehetséges pénzérmekombinációt legalább egyszer. (Többször is.) Ezért aztán biztosan megtalálja a legkisebb értékűt (ezt már bizonyítottuk az előbb is), viszont a futási ideje $N^S$-el arányos, ami "nagyon lassú".
A lassúságon kívűl van azonban egy másik probléma is vele: helytelenül kezeli azokat az eseteket, amikben az adott pénzérme-készletből semmilyen módon nem rakható ki a keresett súly. Ilyenkor a visszatérési érték 0 lesz, ami nem minden esetben felel meg. Például: S = 6, a pénzérmék pedig:
A helyes megoldás ilyenkor két darab i=1 pénzérme, azaz MinErtek(6) = 4. Algoritmusunk viszont a ciklusban i=2 esetén a következő eredményt fogja kapni: ertek0:= MinErtek(6-4) + ertek[2] = 0+3 = 3, mert MinErtek(2) = 0 (egy kirakhatatlan súly), tehát a végeredmény is 3 lesz. A megoldás az, hogy kirakhatatlan súly esetén "érvénytelen értékkel" (pl. -1) tér vissza a függvény, és azt le is kezeli. A módosított algoritmus minimum-kiválasztó része:
MinErtek(S)
Ha S <= 0 Akkor MinErtek := 0
Különben
min_ertek := -1;
Ciklus i := 1-től N-ig
S0 := S-suly[i];
Ha S0 >= 0 Akkor
ertek0 := MinErtek(S0);
Ha (ertek0 >= 0) Akkor
ertek0 := ertek0 + ertek[i];
Ha (ertek0 < min_ertek) vagy
(min_ertek = -1) Akkor
min_ertek := ertek0;
Elágazás vége
Elágazás vége
Elágazás vége
Ciklus vége
MinErtek := min_ertek;
Elágazás vége
Eljárás vége
Módosított algoritmusunk már helyesen számítja ki a minimális értéket, de még mindig nagyon lassú. Ezen könnyen segíthetünk a feljegyzéses módszerrel, mert a függvény visszatérési értékét elég minden S-re egyszer kiszámítani. Vegyünk fel egy globális cache[] tömböt ezen értékek tárolására! Kezdetben minden eleme -2.
MinErtek(S):
Ha cache[s] = -2 Akkor
Elágazás vége
MinErtek:= cache[s];
Eljárás vége
A {...} helyére az algoritmus előző változatát kell írni, annyi módosítással, hogy a kiszámított értéket a cache[s] helyre kell rakni a vissztérés helyett.
(Természetesen a -1-et is.)
Így már csak S-szer fut le a MinErtek(S) függvény, tehát már "elég gyors" az algoritmusunk.
2.Megoldás - Dinamikus Programozással
Egyszerűbbé tehetjük az algoritmusunkat, és kiküszöbölhetjük a rekurziót, ha észrevesszük, hogy a MinErtek(S) függvény mindig csak S-nél kisebb paraméterekkel hívja meg magát, tehát a cache[] tömb az index szerint növekvő sorrendben töltődik fel. Ezért megtehetjük, hogy a MinErtek() függvényt sorban S: 1,2,...S paraméterekre hívjuk meg. Ekkor ráadásul a függvénytörzsből elhagyható a cache[s] = -2 vizsgálat is, mert biztos, hogy még nem számoltuk ki az S súlyhoz tartozó értéket. Az eljáráson belül pedig a MinErtek(S0) függvényhívások lecserélhetőek cache[s0] tömbhivatkozásokra, mert az S-nél kisebb súlyokhoz tartozó értékeket már biztosan kiszámoltuk. Ekkor a főprogram valahogy így fog kinézni:
Ciklus i:= 1-től S-ig
cache[i]:= MinErtek(i);
Ciklus vége
A végeredmény a cache[s] helyen fog megjelenni.
Megoldások:
