Rešitev: 0-1 nahrbtnik (Mathematica)

Iz MaFiRaWiki

Naloga: 0-1 nahrbtnik

Poseben primer problema nahrbtnika je problem, pri katerem elementov ne smemo rezati. Požrešna metoda ne vrne nujno optimalne rešitve.

 Clear[Nah01]
 Nah01[M_Integer, v_List, c_List] /; Length[v] == Length[c] :=  
   Module[{n, p, d, u, uD, uP, uV, sU, px},
   n = Length[v];                                            (* Število vseh predmetov. *)
   p = Range[n];                                             (* Oznake predmetov. *)
   d = c/v;                                                  (* Dragocenosti predmetov. *)
   
   (* Predmete uredimo po dragocenostih. *)
   u = Transpose[Reverse[Sort[Transpose[{d, p}]]]];
   
   (* Seznama urejenih dragocenosti in pripadajočih predmetov. *)
   uD = u[1]; uP = u[2];
   
   (* Velikosti v istem vrstnem redu kot predmeti. *)
   uV = v[uP];
   
   (* V nahrbtnik dodajamo predmete dokler ne presežemo velikosti nahrbtnika. 
    Element, ki je bil v nahrbtnik  dodan nazadnje, razrežemo. *)
   sU = Table[Sum[uV[i], {i, k}], {k, n}];
   px = Table[If[sU[i] < M, 1, 0], {i, n}];
   
   (* Vrnemo seznam izbranih elementov v pravem vrstnem redu. *)
   Last[Transpose[Sort[Transpose[{uP, px}]]]]
   ]

Primer:

 v = {3, 2, 2};
 c = {9, 5, 5};
 M = 4;
 Nah01[M, v, c]
 Cena[c, %]
 Zaseden[v, %%]

Dobimo rezultat, ki pa ni optimalen:

 {1, 0, 0}
 9
 3

V našem primeru bi namreč bil optimalen rezultat s ceno 10 in s polno zasedenostjo nahrbtnika, ki je 4. Vzeti bi morali torej drugi in tretji predmet in ne samo prvega.

Glej tudi

Osebna orodja