Programozás‎ > ‎Feladatok‎ > ‎Hátizsák probléma‎ > ‎

Megoldás

Algoritmus

Mohó algoritmus

Ha a tárgyak helyett tetszőlegesen kis részekre osztható anyagokkal (például aranypor, liszt, olaj) lenne dolga a betörőnek, akkor nyilván azokkal éri meg kezdenie a bepakolást, amelyek egységnyi tömegre eső értéke maximális. Ebben az esetben tehát a következőt teheti:

az anyagok rendezése e[i] / m[i] szerint csökkenően
Ciklus az anyagokon a rendezési sorrendben
    Ha még van hely a zsákban, akkor
        az aktuális anyagból annyi bepakolása, amennyi van, illetve amennyi fér
    Elágazás vége

Ciklus vége

Ha visszatérünk az eredeti feladatra, akkor könnyen látható, hogy a fenti mohó algoritmus nem ad optimális megoldást. Arra viszont jó, hogy legyen egy közelítésünk, amit megpróbálhatunk javítani.

Dinamikus programozás

Ha a tárgyak maximális számának és a hátizsák kapacitásának szorzata nem túl nagy (  < 10), akkor megkaphatjuk a pontos optimumot a dinamikus programozás módszerét alkalmazva.

A megoldást két lépésben ismertetjük:

A feladat átfogalmazása egy rekurzív függvény értékének kiszámítására

Jelentse opt(n, k) azt, hogy az 1., 2., ...,n. tárgyat használva legfeljebb mennyi érték pakolható egy k kapacitású zsákba. Ekkor igazak a következők:

    opt(0, k) = opt(n, 0) = 0

    opt(n, k) = max{opt(n-1, k), opt(n-1, k-m[n])+e[n]}  ha n és k > 0 

A maximumban szereplő második eset persze csak akkor fordul elő, ha k - m[n] nem negatív.

A rekurzív hívások számának csökkentése a feljegyzéses módszer segítségével

Ez lényegében automatikusan megy. Megnézzük, hogy a függvényünk hány különböző paraméter-párra lehet meghívva. Ha ez a szám nem túl nagy, akkor felveszünk egy akkora tömböt, ami az összes kombináció tárolására elég. Amikor először hívódik meg egy adott párra a függvény, akkor kiszámoljuk és eltároljuk a kapott eredményt. Amikor később újra ugyanazokkal a paraméterekkel hívnánk meg, akkor csak elővesszük a táblázatból a már korábban kiszámolt értékeket.

Nyilván akkor gyorsít sokat ez a feljegyzés, ha olyan a probléma szerkezete, hogy a sima rekurzió nagyon sok hívást ismételne.

Hat tárggyal, és 15 kapacitású zsákkal például így nézhet ki a tömbünk (a színezés magyarázata később):

A függvény megvalósítása táblázatkezelőben pedig így:


A képlet kiemelve:

=MAX(
    C4;
    HA($B4>=D$20;
        D$21+INDEX(opt;SOR(C4)-SOR($B$2)-D$20;OSZLOP(C4)-OSZLOP($B$2));
        0
    )
)

Itt opt a C3:I18 tartomény neve.

A kiválasztott tárgyak kiolvasása az opt tömbből

A fenti példában ismerjük, hogy az optimális érték 118. Ezt kékre színeztük az utolsó oszlop utolsó sorában. Tőle balra kisebb érték áll, vagyis az utolsó döntésnél be kellett választanunk az n. tárgyat a 118-as érték eléréséhez. Mivel az utolsó tárgy tömege 6, értéke pedig 23, ezért az első 5 tárgy felhasználásával egy 15-6 = 9 kapacitású zsákba kell 118-23 = 95 értéket bepakolnunk. Ezért az 5. oszlop 9. sorában kékre színezzük a 95 értéket. Látható, hogy így visszafelé lépegetve megkapható egy olyan kiválasztási sorozat, ami az adott kapacitásban megadja az optimális értéket. (Az nem biztos, hogy a kiválasztott tárgyak halmaza egyértelmű.)

A memóriaigény csökkentése abban az esetben, ha csak az optimum értéke kell

Vegyük észre, hogy az n tárgyat használó megoldások értéke csak az n-1 tárgyat használó értékektől függ közvetlenül, azokból kiszámítható. Elég tehát a fenti táblázat utolsó két oszlopát tárolni. Praktikusan ez úgy oldható meg, hogy egy kétoszlopos tömbben nyomon követjük, melyik oszlopot tekintjük "réginek" és melyiket "újnak".

Kódok

Fehér Balázs (C++): hatizsak.cpp
Tegzes Tamás (pascal): hatizsak.pas
Hornák Bence (C++): hb_hatizsak.cpp
Gedai Bence (C#): gb_hatizsak.cs