Informatika gyűjtemény

Egy szinttel feljebb Megoldás

2004050607080910

NézetNyomtat

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); {1}
        Ha marad >= s[hely] Akkor
            ertek0:= e[hely] + 
                Legjobb(hely+1, marad-s[hely]); {2}
            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); {1}
            choice[hely, marad]:= Hamis;
            Ha marad >= s[hely] Akkor
                ertek0:= e[hely] + 
                    Legjobb(hely+1, marad-s[hely]); {2}
                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