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

Iz MaFiRaWiki

Problem 0-1 nahrbtnika

Problem 0-1 nahrbtnika je poseben primer celoštevilskega programiranja.
Rešimo ga lahko z dinamičnim programiranjem.

Naj bo M velikost nahrbtnika.
Naj bo n število predmetov.

Naj bo c=(c_{1}, \ldots, c_{n}) vektor cen predmetov, kjer je ci cena i-tega predmeta.
Naj bo v=(v_{1}, \ldots, v_{n}) vektor velikosti predmetov, kjer je vi velikost i-tega predmeta.

Naj bo x=(x_{1}, \ldots, x_{n}) vektor predmetov, ki smo jih dali v nahrbtnik.
Imamo dve možnosti:
- xi = 0, kar pomeni, da i-tega predmeta ne damo v nahrbtnik
- xi = 1, kar pomeni, da i-ti predmet damo v nahrbtnik

Iščemo tak vektor x, da bo veljalo:
- \sum_{i=1}^{n}(v_{i} \cdot x_{i}) \leq M
- C= \max \sum_{i=1}^{n}(c_{i} \cdot x_{i})

In[1]:=  Clear[c, v, M]
In[2]:=  c = {3, 5, 7, 8};
         v = {2, 4, 4, 6};
         M = 9;

Dobili smo:
C = 12 in x = (0,1,1,0)

Algoritem 0-1 nahrbtnika (dinamično programiranje)

Dinamično programiranje brez vektorja izbire

In[5]:=  Clear[Nahrbtnik]
In[6]:=  Nahrbtnik[c_List, v_List, M_Integer] /; (Length[c] == 0) = 0;

         Nahrbtnik[c_List, v_List, M_Integer] /; (M ≥ First[v]) := Nahrbtnik[c, v, M] = Max[
         First[c] + Nahrbtnik[Rest[c], Rest[v], M - First[v]], Nahrbtnik[Rest[c], Rest[v], M]
         ];

         Nahrbtnik[c_List, v_List, M_Integer] := Nahrbtnik[c, v, M] = Nahrbtnik[Rest[c], Rest[v], M];

In[9]:=  Nahrbtnik[c, v, M]
Out[9]=  12

Dinamično programiranje z vektorjem izbire

In[10]:= Clear[Nahrbtnik]
In[11]:= Nahrbtnik[c_List, v_List, M_Integer] /; (Length[c] == 0) = {0, {}};

         Nahrbtnik[c_List, v_List, M_Integer] /; (M ≥ First[v]) := Nahrbtnik[c, v, M] = Module[{f1, f2},
          f1 = Nahrbtnik[Rest[c], Rest[v], M - First[v]];
          f2 = Nahrbtnik[Rest[c], Rest[v], M];
          If[
           First[c] + First[f1] > First[f2],
           {First[c] + First[f1], Prepend[Last[f1], 1]},
           {First[f2], Prepend[Last[f2], 0]}
          ]
         ];

         Nahrbtnik[c_List, v_List, M_Integer] := Nahrbtnik[c, v, M] = Module[{f1},
         f1 = Nahrbtnik[Rest[c], Rest[v], M];
         {First[f1], Prepend[Last[f1], 0]}
         ];

In[14]:= Nahrbtnik[c, v, M]
Out[14]= {12, {0, 1, 1, 0}}

Primer uporabe

In[15]:= Clear[cc,ww,MM]
In[16]:= cc=Table[Random[Integer,100],{10}]
         vv=Table[Random[Integer,100],{10}]
         MM=Apply[Plus,vv]-100
Out[16]= {56, 73, 65, 37, 75, 23, 65, 97, 38, 26}
Out[17]= {18, 52, 80, 43, 4, 48, 68, 13, 20, 82}
Out[18]= 328

In[19]:= Clear[c,v,M]
In[20]:= c={39, 80, 64, 63, 75, 30, 99, 56, 88, 64};
         v={85, 49, 56, 18, 35, 67, 54, 37, 38, 56};
         M=395;
In[23]:= Nahrbtnik[c,v,M]
Out[23]= {589, {0, 1, 1, 1, 1, 0, 1, 1, 1, 1}}
Osebna orodja