1. megoldás - rekurzióvalEhhez 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:
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 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ássalEgyszerű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 MegvalósításokFehér Gábor (Delph): fg_mal.dpr Tihanyi Balázs (Visual Basic.NET): tb_mal.vb Mészáros Balázs (C): mb_mal.c Kriván Bálint (C#): kb_mal.cs |