0/1 nahrbtnik

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina

Problem 0/1 nahrbtnika

S problemom napolniti nahrbtnik se srečamo kaj pogosto, v tej ali v oni preobleki, če že ne drugače, pa vsaj tedaj, ko doma ugotavljamo, da je nahrbtnik mnogo premajhen, predmetov, ki jih želimo vzeti seboj, pa mnogo preveč. Tako nas izkušnje uče, da je napolniti nahrbtnik težak problem.

Imamo majhen nahrbtnik volumna V\ge0 ter n predmetov velikosti v_i (0<v_i\leq V) in cen ci, ki bi jih radi dali v nahrbtnik.
Predmet lahko damo v nahrbtnik cel ali pa sploh ne:

  • če je xi = 1, i-ti predmet je v nahrbtniku
  • če je xi = 0, sicer

Od tod torej ime 0/1 nahrbtnik.

Iščemo tako razporeditev x_i,\quad i = 1 , 2, ..., n, ki nam da največjo vrednost

C =\max \sum_{i=1}^{n} c_{i}x_{i}

pri omejitvah

\sum_{i=1}^{n} v_{i}x_{i} \leq V

Požrešna metoda

Eden izmed načinov za reševanje problema nahrbtnika je požrešna metoda, kjer na vsakem koraku vzamemo tisti element, ki ima največjo relativno vrednost \frac{c_{i}}{v_{i}}. Četudi nas ta metoda v primeru, ko predmete lahko režemo (preprost problem nahrbtnika, kar pomeni, da je 0\leq x_i\leq 1), vedno pripelje do optimalne rešitve, za 0/1 nahrbtnik pa to ni nujno res.

Primer

Nahrbtnik:
n = 2
c = (1,3)
v = (1,4)
V = 4

     
  • Rešitev s požrešno metodo:
\frac{c_{i}}{v_{i}} = (1, 0.75)
x = (1,0)
C = 1
     
  • Boljša rešitev:
x = (0,1)
C = 3

Vodimo več potencialnih rešitev, pri katerih vsako preverimo ter jo zavržemo, če ne pelje k rešitvi.

Diskretno dinamično programiranje

Za 0/1 nahrbtnik velja pravilo optimalnosti, ki pravi, da je zaporedje odločitev optimalno, če in samo če je tudi vsako podzaporedje tega zaporedja odločitev tudi samo optimalno.

Če z Gi(W) označimo vrednost optimalne rešitve manjše naloge s predmeti z indeksi 1,...,i in prostim volumnom W, dobimo Bellmanove enačbe, imenovane po očetu dinamičnega programiranja Bellmanu:

Gi(W) = max{Gi − 1(W),Gi − 1(Wvi) + ci}, za i = 1,2,...,n. 

z začetnimi pogoji

G_0(W) = -\infty, če je W < 0 (nimamo predmetov, prostora v nahrbtniku pa tudi ne) 
G0(W) = 0, če je W\geq 0 (nimamo predmetov, prostor v nahrbtniku pa) 

Z izbiro -\infty pri negativnem volumnu preprečimo, da bi vzeli predmete, ki ne gredo noter, ker "neskončno pokvarijo" vrednost. S tem maksimum ne bo nikoli napačen!

Implementacija

Rekurzivna rešitev

  1. O_1Nahrbtnik(i, W) {
  2. if (i = 0)
  3. if (W >= 0) return 0;
  4. else return -∞;
  5. neVzamem = O_1Nahrbtnik(i-1,W);
  6. vzamem = O_1Nahrbtnik(i-1,W-v[i])+c[i];
  7. return max(neVzamem, vzamem);
  8. }

Klic:

  1. O_1Nahrbtnik(n,V);

Časovna zahtevnost: O(2n)

Ta rešitev ni unčinkovita, ker veliko vozlišč izračunamo večkrat ali celo odveč.

Primer:
n=5, V=10, w=[2, 2, 6, 5, 4], c=[6, 3, 5, 4, 6]

Rešitev z zlivanjem

Gj(W) je odsekoma konstantna funkcija, zato si moramo zapomniti le točke skokov. kar popišemo s seznamom parov (abcise skoka, ordinate skoka):

Si = {množica parov (W,C), ki opisuje Gi(W)}

Kot vemo, je: S0 = (0,0)

Denimo, da poznamo Si − 1. Ko sestavljamo Si moramo poiskati

Zi = {množica parov (W,C): (W-v_i,C-c_i) \in S_{i-1}\}

Množica Zi nam definira zamik in dvig gi(W) (za vi v desno in za ci navzgor). Nato zlijemo Si − 1 in Zi v Si tako, da bo nova funkcija maksimum obeh prejšnjih.

Primer:

n = 4
V = 9
v = (4, 2, 4, 6)
c = (5, 3, 7, 8)
Zaradi zlivanja uredimo v in c nepadajoče:
v = (2, 4, 4, 6)
c = (3, 5, 7, 8)
S0 = {(0,0)}
Z1 = {(0 + 2,0 + 3)} = (2,3)
S1 = {(0,0),(2,3)}
Z2 = {(0 + 4,0 + 5),(2 + 4,3 + 5)} = (4,5),(6,8)
S2 = {(0,0),(2,3),(4,5),(6,8)}
Z3 = S2 + (4,7) = {(4,7),(6,10),(8,12),(10,15)}
S3 = {(0,0),(2,3),(4,7),(6,10),(8,12),(10,15)}
Z4 = S3 + (6,8) = {(6,8),(8,11),(10,15),(12,18),(14,20),(16,23)}
S4 = {(0,0),(2,3),(4,7),(6,10),(8,12),(10,15),(12,18),(14,20),(16,23)}

Tako dobimo, da je optimum 12, pri tem pa zasedemo 8 enot volumna.

Sedaj moramo dobiti še rešitev x.
Pare vodimo le dokler ne presežejo V. Z (W * ,C * ) označimo zadnji par v Sn, kjer je W^*\leq V. Torej, v W * imamo skok na C * , kar pomeni, da je to skok v Sn − 1 ali pa v Zn. V prvem primeru je xn = 0, v drugem pa xn = 1. Če je (W * ,C * ) tako v Sn − 1 kot v Zn, pomeni to da obstajata dve optimalni rešitvi z isto vrednostjo in isto skupno velikostjo, od katerih ena vsebuje zadnji predmet, druga pa ne. Odločimo se lahko za prvo ali drugo možnost.
Ko poznamo komponento xn, nadaljujemo na enak način z določanjem vrednosti za xn − 1, kjer v primeru xn = 1 vrednost tekočega skoka zmanjšamo v

(W^*,C^*)\rightarrow (W^*-v_n,C^*-c_n).

Postopek ponavljamo v globino, da izsledimo vse x_i,\quad i=n,n-1,...,1

V našem primeru bo to:

(8,12)\in S_3 \rightarrow  x_4 = 0
(8,12)\notin S_2 \rightarrow x_3 = 1:(8,12)-(4,7)\in S_2
(4,5)\notin S_1 \rightarrow x_2 = 1:(4,5)-(4,5)\in S_1
(0,0) \in S_0 \rightarrow  x_1 = 0

Rešitev je torej (0, 1, 1, 0).

Glej tudi

Osebna orodja