Rešitev: 0-1 nahrbtnik (dinamično programiranje), druga rešitev (Mathematica)

Iz MaFiRaWiki

Naloga: 0-1 nahrbtnik (dinamično programiranje)

Najprej definiramo funkcijo pari, ki tvori seznam parov (velikost,cena) za vsak element, ki gre lahko v nahrbtnik. Z n označimo število elementov, ki jih imamo na voljo. Velikost in ceno elementov podamo z vektorjema v in c.

 n/;Length[v]==Length[c] := Length[v]
 pari = {};
 
 For[i = 1, i <= n,
   par := {{v[[i]], c[[i]]}};
   pari = Join [pari, par];
   i++;
   ]

Funkcija loci v primeru, ce imata dva elementa enako velikost, izbere tistega z vecjo ceno. Funkcija lociBrisi pa izpusti tiste elemente, pri katerih velikost (po preracunavanju v algoritmu) presega velikost nahrbtnika (W). Ti dve funkciji predstavljata operacijo *unija*.

 loci[dvaPara_List] := ((If[#1[[1]][[1]] == #1[[2]][[1]],
               {#1[[2]]},
               #1]) &)[dvaPara];
 lociBrisi[dvaPara_List] := Select[loci[dvaPara], #[[1]] <= W &];

Definiramo S in Z kot v opisu algoritma. Ss so prave vrednosti S za nek j, kjer so nepotrebni elementi izpusceni s funkcijo "lociBrisi " (opis zgoraj).

 S[0] := {{0, 0}};
 For[j = 1, j <= n,
   Z[j] = S[j - 1] + Table[pari[[j]], {i, Length[S[j - 1]]}];
   Flatten[Map[lociBrisi, Partition[Z[j], 2, 2]], 1];
   S[j] = Union[S[j - 1], Z[j]];
   Ss[j] = Flatten[Map[lociBrisi, Partition[S[j], 2, 2]], 1];
   j++;
  ];

Resitev je par v Ss[n], ki ima najvecjo ceno. Prvi element v paru je koncna velikost optimalne, najboljse resitve,drugi element pa je koncna cena optimalne resitve.

Resitev := Last[Ss[n]];

Sedaj definiramo še funkcijo g kot v opisu algoritma. Izpostavimo primera, ko imamo podano velikost nahrbtnika, nimamo pa nobenih predmetov ter primer ko nimamo niti predmetov, niti nahrbtnika.

 g[0, W_] /; W >= 0 := g[0, W] /; W >= 0 = {0, Table[0, {Length[v]}]}
 g[0, W_] /; W < 0 := g[0, W] /; W < 0 = {-\[Infinity], Table[0, {Length[v]}]}

 g[i_, W_] := g[i, W] = Module[{dober, x},              
       dober = Max[{g[i - 1, W][[1]], g[i - 1, W - v[[i]]][[1]] + c[[i]]}];
       If[Position[{g[i - 1, W][[1]], g[i - 1, W - v[[i]]][[1]] + c[[i]]}, dober][[1]][[1]] == 2,
         x = ReplacePart[g[i - 1, W - v[[i]]][[2]], 1, i],
         x = g[i - 1, W][[2]]];
       Return[{dober, x}]
      ]

Še uredimo izpis rešitve:

 elementi = Part[g[Length[v], W], 2];
 
 Print["Re\[SHacek]itev je slede\[CHacek]a: "]
 Print["*  ", elementi , " je seznam elementov, ki jih damo v nahrbtnik."]
 Print["*  ", Resitev[[2]], " je cena elementov, ki jih damo v nahrbtnik."]
 Print["*  ", Resitev[[1]], " je velikost elementov, ki jih damo v nahtbnik."]

Preizkusimo na šolskem primeru:

 W = 9;
 v = {2,4,4,6};
 c = {3,5,7,8};
 
 Rešitev je sledeča: 
 {0,1,1,0} je seznam elementov, ki jih damo v nahrbtnik.
 12 je cena elementov, ki jih damo v nahrbtnik.
 8 je velikost elementov, ki jih damo v nahtbnik.

Glej tudi

Osebna orodja