Rešitev: 01 nahrbtnik s sestopanjem (Mathematica)

Iz MaFiRaWiki

Naloga: 01 nahrbtnik s sestopanjem

Pomožne funkcije:

Vsota[l_List, i_Integer] := Apply[Plus, Take[l, i]]
Vsota[l_List] := Vsota[l, Length[l]]
Vsota[l_List, m_List] := Vsota[Part[l, m]]
Vsota::usage  = 
  "Vsota[seznam] nam vrne vsoto števil v seznamu. Če je podan le 
seznam, vrne vsoto vseh števil v seznamu, če je podano še število i, 
vrne vsoto vseh prvih i števil v seznamu, če je podan še en seznam, 
vrne vsoto števil, ki so na izbranih mestih v prvem seznamu.";

Notri[l_List] := Module[{s},
  s = {};
  For[i = 1, i <= Length[l], i++,
   If[l[[i]] == 1, s = Append[s, i]]
   ];
  s
  ]
Notri::usage  = 
  "Notri[seznam] nam kot seznam vrne indekse števil, ki so v naši 
trenutni kombinaciji.";

EnkeDoN[n_] := Module[{f, s},
  f[k2_][k1_] := If[k1 <= k2, 1, 0];
  s = {};
  For[i = 1, i <= n, i++,
   s = Append[s, Array[f[i], n]];
   ];
  s
  ]
EnkeDoN::usage = 
  "EnkeDoN[n] nam vrne seznam seznamov dolžine n, v katerih gre 
število enic od 1 do n.";

VseMoznosti[n_] := Flatten[Map[Permutations, EnkeDoN[n]], 1]
VseMoznosti::usage  = 
  "VseMoznosti nam vrne vse možne kombinacije števil, ki bi jih lahko 
izbrali za našo napolnitev nahrbtnika.";

Funkcija Napolni01Nahrbtnik:

Napolni01Nahrbtnik[M_Integer, v_List, c_List] := Module[{L, x, X, a},
  L = Length[v];
  x = VseMoznosti[L];
  X = Table[0, {L}];
  If[Length[v] != Length[c], X = "Nepopolni podatki", 
   a = 1;
   While[a <= Length[x],
    If[Vsota[v, Notri[ x[[a]] ] ] <= M && 
      Vsota[c, Notri[ x[[a]] ] ] >= Vsota[c, Notri[X]],
     X = x[[a]];
     ];
    a++;
    ];
   Print["Zapolnjen volumen:"];
   Print[Vsota[v, Notri[X]]];
   Print["Celotna vrednost nahrbtnika:"];
   Print[Vsota[c, Notri[X]]];
   ];
  X
  ]
Napolni01Nahrbtnik::usage  = 
  "Napolni01Nahrbtnik[Velikost_Nahrbtnika, Seznam_Velikosti_Elementov, Seznam_Cen_Elementov] 
nam vrne seznam ničel in enic, ki nam povedo, katere elemente moramo zložiti v 
01-nahrbtnik, da bo ta optimalno napolnjen. Izpiše nam še, kako 
zapolnjen je nahrbtnik in kakšna je njegova vrednost.";

Primeri:

In[13]:= Napolni01Nahrbtnik[4, {1, 4}, {1, 3}]
        
         Zapolnjen volumen:
         4
         Celotna vrednost nahrbtnika:
         3
Out[13]= {0, 1}
In[14]:= Napolni01Nahrbtnik[9, {2, 4, 4, 6}, {3, 5, 7, 8}]
        
         Zapolnjen volumen:
         8
         Celotna vrednost nahrbtnika:
         12
Out[14]= {0, 1, 1, 0}
In[15]:= Napolni01Nahrbtnik[4, {3, 2, 2}, {9, 5, 5}]
        
         Zapolnjen volumen:
         4
         Celotna vrednost nahrbtnika:
         10
Out[15]= {0, 1, 1}
In[16]:= Napolni01Nahrbtnik[4, {7, 5, 9}, {9, 5, 5}]
        
         Zapolnjen volumen:
         0
         Celotna vrednost nahrbtnika:
         0
Out[16]= {0, 0, 0}
In[17]:= Napolni01Nahrbtnik[64, {3, 11, 21, 22, 14, 4, 16, 19, 3, 7, 5, 9, 5}, {9, 5, 8, 3, 5, 7, 
  8, 17, 3, 13, 7, 1, 4}]
        
         Zapolnjen volumen:
         62
         Celotna vrednost nahrbtnika:
         68
Out[17]= {1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1}
In[18]:= Napolni01Nahrbtnik[79, {7, 5, 9}, {9, 5, 5, 7}]
        
Out[18]= Nepopolni podatki


Glej tudi

Osebna orodja