Izpitno vprašanje RAČ2PRA 17100

Iz MaFiRaWiki

Vprašanje

Problem 0/1 nahrbtnika

Odgovor

Problem podoben preprostemu problemu nahrbtnika, razlika je le v tem, da je v nahrbtniku lahko samo cel predmet (1) ali pa v nahrbtniku predmeta ni (0). Od tod tudi ime 0/1 problem nahrbtnika.

Podano je n predmetov, pri čemer ima i-ti predmet prostornino vi in vrednost ci. Če imamo nahrbtnik s prostornino V, se postavlja problem izbire take podmnožice predmetov, ki ima največjo skupno vrednost (vsota vrednosti predmetov v podmnožici), obenem pa po skupni prostornini ne presega V. Torej,

\sum_{i=1}^n x_iv_i \le V
\sum x_ic_i \le V
maksimalno, x_i\in{0,1}.

Problem bomo rešili tako, da ga bomo najprej razcepili na podprobleme, nato pa slednje reševali po velikosti (začeli bomo z najmanjšimi). S ki(W) bomo označevali vrednost optimalnega nahrbtnika, ki ima skupno prostornino W, če upoštevamo le prvih i predmetov. Bodimo pozorni, da je ki, funkcija enega argumenta, katere vrednost je izražena v istih enotah kot vrednosti predmetov, ci. Očitno v tem primeru velja

ki(W)=MAX(ki − 1(W),ki − 1(W-vi)+ci).

Razlaga zgornje enačbe, ki ji pravimo Bellmanova enačba, je, da moramo pri odločitvi, ali predmet i pripada optimalni podmnožici predmetov, primerjati optimalno vrednost nahrbtnika z upoštevanjem i - 1 predmetov, kar ustreza primeru, ko i - 1 predmet NI vključen v optimalno podmnožico, z optimalno vrednostjo, ko je i-ti predmet vključen, ta pa je enaka optimalni množici z upoštevanjem i -1 predmetov, vendar pri prostornini, ki je zmanjšana za prostornino i-tega predmeta in z vrednostjo, ki smo ji dodali vrednost i-tega predmeta. Rešitev prvotne naloge je kn(V).

Primer praktičnega vidika reševanja problema, ki privede do optimalne rešitve.

Problem rešimo v dveh fazah:

  • Gradnja rešitve, tako da vodimo vse pare (volumen, cena),
  • Rekonstrukcija rešitev

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 Sk kot množica parov (volumen, cena), ki predstavljajo možne rešitve tega problema, pri čemer začetna množica S0 = {(0, 0)} predstavlja prazne 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 potencialnih elementov

Pričnemo z začetno množico S0 = {(0, 0)} in zatem, kakor da bi vstavili prvi element oz. par (2, 3):

S0 = {(0, 0)} Z1 = {(0 + 2, 0 + 3)} = {(2, 3)}

Vse elemente iz Z1 prepišemo v S1 in pri istem volumnu zapišemo samo par z največjo ceno. Sledi naslednji element (4, 5):

S1 = {(0, 0), (2, 3)} Z2 = {(0 + 4, 0 + 5),(2 + 4, 3 + 5)} = {(4, 5),(6, 8)}

Vse elemente iz Z2 prepišemo v S2 (dobro je, da so urejeni po velikosti cene). Tretji element za vstavit je par (4, 7):

S2 = {(0, 0), (2, 3), (4, 5),(6, 8)} Z3 = {(0 + 4, 0 + 7), (2 + 4, 3 + 7), (4 + 4, 5 + 7),(6 + 4, 8 + 7)} = {(4, 7), (6, 10), (8, 12), |(10, 159)}

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

S3 = {(0, 0), (2, 3), (4, 7), (6, 10), (8, 12)} Z3 = {(6, 8),(8, 11), | … vsi ostali …}

In na koncu S_4, ki je v tem primeru slučajno tudi enak S_3:

S4 = {(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 S4) 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 Sk, ne pa tudi v Sk − 1, smo do tega para zagotovo prišli tako, da smo dodali k-ti element. In če obstaja, odštejemo vrednosti tega elementa od para in ponovimo iskanje parov do začetne množice S0. Nadaljevanje primera bi tako bilo:

  1. Ker (8, 12) \in S4 in (8, 12) \in S3 dobimo, da četrti element (6, 8) ni v optimalni rešitvi.
  2. Ker (8, 12)\in S3 in (8, 12) \notin S2 dobimo, da je tretji element (4, 7) v optimalni rešitvi. Odštejemo vrednost tega elementa in dalje iščemo par (8-4,12-7) = (4, 5).
  3. Ker (4, 5) \in S2 in (4, 5) \notin S1, je drugi element (4, 5) v optimalni rešitvi. Dalje iščemo par (0, 0) …

Glej tudi

Osebna orodja