0-1 nahrbtnik

Problem 0-1 nahrbtnika rešujemo v dveh fazah:

• gradnja rešitve, tako da vodimo vse pare (volumen, cena),
• rekonstrukcija rešitve.

Prva faza

V prvi fazi gradimo možne rešitve in sproti zavračamo tiste, kjer je volumen večji od razpoložljivega. Zamislimo si zapis S_k kot množico parov (volumen, cena), ki predstavljajo možne rešitve tega problema, pri čemer začetna množica S₀ = {(0, 0)} predstavlja prazen nahrbtnik. Zatem za vsak potencialni element ponovimo enak postopek: izračunamo vse pare (volumen, cena), kakor da bi ta element "vstavili" v nahrbtnik. Pokažimo to na primeru: n = 4 (število potencialnih elementov za v nahrbtnik).

V = 9 ... volumen nahrbtnika
v = (2, 4, 4, 6) ... volumni potencialnih elementov
c = (3, 5, 7, 8) ... cene (korist) potencialnih elementov

Pričnemo z začetno množico S₀ = {(0, 0)} in v nahrbtnik "vstavimo" prvi element oz. par (2, 3). Dobimo:

S₀ = { (0, 0) }
Z₁ = { (0 + 2, 0 + 3) } = { (2, 3) }


Vse elemente iz Z₁ prepišemo v S₁ (iz Z₁ in S₀, oziroma bolj splošno iz Z_k in S_k-1) po postopku --> Pri tistih elementih, ki:

• imajo isti volumen, zapišemo samo tistega, ki ima največjo ceno ter
• pri tistih elementih, ki imajo isto ceno, zapišemo tistega, ki ima manjši volumen.

S tem zagotavljamo, da imamo lahko v nahrbtniku najvec najbolj vrednih predmetov. Sledi naslednji element (4, 5). Dobimo:

S₁ = { (0, 0), (2, 3) }
Z₂ = { (0 + 4, 0 + 5), (2 + 4, 3 + 5) } = { (4, 5), (6, 8) }


Vse elemente iz Z₂ prepišemo v S₂ (dobro je, da so urejeni po velikosti cene). Tretji element za vstavit je začetni par (4, 7) in dobimo:

S₂ = { (0, 0), (2, 3), (4, 5), (6, 8) }
Z₃ = { (0 + 4, 0 + 7), (2 + 4, 3 + 7), (4 + 4, 5 + 7), (6 + 4, 8 + 7) } = { (4, 7), (6, 10), (8, 12) | (10, 15) }


Par (10, 15) je namensko zapisan za znakom |, ki označuje, da ta rešitev več ni primerna, ker je volumen vstavljenih elementov že večji od razpoložljivega. Po vstavljanju zadnjega para (6, 8) dobimo:

Bodite pozorni na to, da smo element (4, 5) v S3 iz S2 zamenjali z elementom (4, 7), ki smo ga dobili v Z3,
ker je imel isti volumen in večjo ceno. Enako velja za element (6, 8), ki smo ga zamenjali z elementom (6, 10).

S₃ = { (0, 0), (2, 3), (4, 7), (6, 10), (8, 12) }
Z₄ = { (6, 8), (8, 11), | ... ter vsi ostali elementi, katerih skupen volumen presega volumen nahrbtnika in nas zato ne zanimajo... }


Na koncu dobimo S₄, ki pa je v tem primeru slučajno tudi enak S₃:

S₄ = { (0, 0), (2, 3), (4, 7), (6, 10), (8, 12) }

Druga faza

V drugi fazi rekonstruiramo rešitev oziroma poiščemo kateri elementi bodo zares vstavljeni v nahrbtnik. Iz končne množice (v našem primeru S₄) izberemo par z največjo ceno, kar za naš primer znaša (8, 12). Zatem "po poti nazaj" gledamo, kako smo prišli do tega para. Če par obstaja v S_k, ne pa tudi v S_k-1, smo do tega para zagotovo prišli tako, da smo v nahrbtnik dodali k-ti element. In če obstaja, odštejemo vrednosti tega elementa od para, ki ga trenutno "držimo" in ponovimo iskanje parov do začetne množice S₀.
Nadaljevanje primera bi tako bilo:

1. Ker je element (8, 12) v S₄ in v S₃ vidimo, da četrti element (začetni par (6, 8)) ni v optimalni rešitvi.
2. Ker je element (8, 12) v S₃, vendar ne v S₂ dobimo, da je tretji element (začetni par (4, 7)) v optimalni rešitvi. Odštejemo vrednost tega elementa, ki ga "držimo" in tretjega elementa, ter dalje iščemo par (8 - 4, 12 - 7) = (4, 5).
3. Ker je element (4, 5) v S₂, vendar ne v S₁, je drugi element (začetni par (4, 5)) v optimalni rešitvi. Dalje iščemo par (4 - 4, 5 - 5) = (0, 0).
4. Ker je element (0, 0) v S₁ in v S₀ vidimo, da prvi element (začetni par (2, 3)) ni v optimalni rešitvi.

Tako dobimo končno rešitev: V optimalni rešitvi (nahrbtniku) sta torej samo drugi in tretji element.


Povzeto po: http://www-mat.pfmb.uni-mb.si/personal/www-kaucic/vaje/2003-2004/alg/sklop5.pdf