Megoldás

Programozás‎ > ‎Feladatok‎ > ‎Malac‎ > ‎

1. megoldás - rekurzióval

Ehhez 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 NS-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áu ha S = 6 és a pénzérmék pedig a következőek:

i	súly	érték
1	3	2
2	4	3

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.