Adatstruktúrák
N darab település van, K a teherautó teherbírása.
Az i-edik településen várakozó csomag súlya: s[i], az elszállításáért felajánlott fizetség pedig e[i].
Rekurzív megfogalmazás
Képzeljünk el egy Legjobb(hely, marad) függvényt, ami megadja, hogy ha marad szabad kapacítással érkezik a teherautó a hely sorszámú településre, akkor mennyi pénzt kereshet még legfeljebb, a hátralévő úton. (azaz a hely, hely+1, ..., N településeken áthaladva.) A Legjobb(1, K) hívás megadja a teljes úton elérhető maximális összhasznot, azaz a keresett végeredményt. A Legjobb függvény megírható egy egyszerű, rekurzív maximum-kiválasztással. Ha a hely sorszámú helyre marad szabad kapacitással érkezve felveszi az ottani csomagot, akkor: e[hely]+Legjobb(hely+1, marad-s[hely]) pénzt fog keresni ({2}), egyébként pedig Legjobb(hely+1, marad) pénzt ({1}).
Legjobb(hely, marad)
Ha hely > N Akkor Legjobb:= 0
Különben
ertek:= Legjobb(hely+1, marad);
Ha marad >= s[hely] Akkor
ertek0:= e[hely] +
Legjobb(hely+1, marad-s[hely]);
Ha ertek0 > ertek Akkor ertek:= ertek0;
Elágazás vége
Legjobb:= ertek;
Elágazás vége
Eljárás vége
Eljárásunk minden településen kétfelé ágazik, aszerint, hogy felveszi az ott lévő csomagot, vagy nem. Így a sebessége $2^N$-el lesz arányos, ami nagyon lassú. A sebességet például a feljegyzéses módszerrel lehet növelni, csak arra vigyázzunk, hogy a visszatérési értékeket most egy két-dimenziós tömbben kell tárolni. (Pl. cache[hely, marad], lásd a következő programpéldát!)
Csomagok kiválasztása
Ha meg akarjuk tudni, hogy mely csomagok felvétele szűkséges a már kiszámolt optimum eléréséhez, akkor több információra van szűkségünk.
Vegyünk fel még egy choice[hely, marad] tömböt, ami minden esetre eltárolja a Legjobb() függvény döntését. Tehát legyen choice[i, j] = Igaz, ha az i-edik városba j szabad kapacitással érkezve megéri felvenni az ottani csomagot ({2}), és legyen Hamis, ha nem éri meg ({1}).
A choice[] és cache[] tömbök feltöltése
Kezdetben cache[] minden eleme -1.
Legjobb(hely, marad)
Ha cache[hely, marad] = -1 akkor
Ha hely > N Akkor cache[hely, marad]:= 0
Különben
ertek:= Legjobb(hely+1, marad);
choice[hely, marad]:= Hamis;
Ha marad >= s[hely] Akkor
ertek0:= e[hely] +
Legjobb(hely+1, marad-s[hely]);
Ha ertek0 > ertek Akkor
ertek:= ertek0;
choice[hely, marad]:= Igaz;
Elágazás vége
Elágazás vége
cache[hely, marad]:= ertek;
Elágazás vége
Elágazás vége
Legjobb:= cache[hely, marad];
Eljárás vége
A choice[] tömbből egy kis logikával már kinyerhetőek az optimumhoz felvett csomagok városainak a sorszámai. Kövessük végig a teherautó útját, vagyis vegyük sorra a városokat 1-től N-ig. Egy adott i városban akkor vette fel a csomagot, ha choice[i, marad] = Igaz. A marad változó értéke a kezdeti K teherbírás, és az i város előtt felvett csomagok összsúlyának a különbsége. Pl. így irathatók ki a kiválasztott csomagok sorszámai:
marad:= K;
Ciklus i:= 1-től N-ig
Ha choice[i, marad] = Igaz Akkor
Kiír(i);
marad:= marad - s[i];
Elágazás Vége
Ciklus vége
Megoldások
