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

Megoldás

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:
isúlyérték
132
243

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.

Megvalósítások

Fehé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
ċ
fg_mal.dpr
(1k)
Gábor Fehér,
2012. jún. 18. 14:17
ċ
kb_mal.cs
(4k)
Gábor Fehér,
2012. jún. 18. 14:17
ċ
mb_mal.c
(1k)
Gábor Fehér,
2012. jún. 18. 14:17
ċ
tb_mal.vb_
(1k)
Gábor Fehér,
2012. jún. 18. 14:18
Comments