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

Iz MaFiRaWiki

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

 Clear[g,v]
 g[0,W_]/;W≥0 := g[0,W]/;W≥0 = {0,Table[0,{Length[v]}]}
 (*Predmetov nimamo, medtem ko nahrbtnik imamo.*)

 g[0,W_]/;W<0 := g[0,W]/;W<0 = {-∞,Table[0,{Length[v]}]}
 (*Predmetov nimamo, niti nimamo nahrbtnika.*)

 g[i_,W_] := g[i,W] =
  Module[{t,M,x},
   t={g[i-1, W][[1]], g[i-1, W-v[[i]]][[1]] + c[[i]]}; (*v[[i]] je velikost i-tega predmeta in c[[i]] je cena i-tega predmeta*)
   M=Max[t];
   (*Če je prvi element tabele t maksimum, pomeni, da je bolje, če i-tega predmeta ne damo v nahrbtnik. Če pa je drugi element 
    maksimum, je bolje, da i-ti element damo v nahrbtnik (skupna cena je višja).*)

   If[Position[t, M][[1]][[1]]==2, x=ReplacePart[g[i-1, W-v[[i]]][[2]], 1, i], x=g[i-1, W][[2]]];
   (*Če je drugi element tabele t maksimum, spremenimo rešitev x "v funkciji na drugem mestu tabele" (na i-tem mestu zamenjamo
    0 z 1). V nasprotnem rešitve ne popravljamo in jo le "prepišemo iz funkcije na prvem mestu tabele".*)

   Return[{M, x}]
  ]
 g::usage="Funkcija g[i,W] vrne seznam z dvema elementoma. Prvi del predstavlja največjo možno skupno ceno ob polnjenju 
  nahrbtnika s težo W s predmeti z indeksi manjšimi ali enakimi i. Drugi del pa nam pove rešitev, to je, katere predmete moramo
  dati v nahrbtnik, da dobimo maksimalno ceno (0 na j-tem mestu rešitve pomeni, da predmeta z indeksom j ne damo v nahrbtnik 
  in 1 pomeni, da ga damo).";

Preizkusimo na primeru:

 Clear[W,v,c]
 W = 9;
 v = {2,4,4,6};
 c = {3,5,7,8};
 In[10]:= g[Length[v], W]
 Out[10]:= {12, {0,1,1,0}}

Glej tudi

Osebna orodja