: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > inne >

P A K O W A N I E   P L E C A K A

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Problem plecakowy formułuje się następująco:

  • mamy do dyspozycji plecak o maksymalnej pojemności b oraz zbiór przedmiotów Z, z których każdy ma określoną objętość v[i] oraz wartość w[i] - należy zapakować plecak przedmiotami zbioru Z w taki sposób, aby suma wartości wszystkich przedmiotów umieszczonych w plecaku miała największą możliwą wartość

Dysponując danymi:

b = 21
v = [ 10,  7,  5,  5 ]
w = [ 20, 15, 11, 12 ]

nie zapakujemy plecaka optymalnie wybierając kolejno przedmioty o coraz większej objętości: v'=[5, 5, 7], w'=12+11+15=38. Również wybierając przedmioty w sposób zachłanny kolejno od tych, dla których stosunek wartości do objętości (czyli wartość jednostkowa) jest największy: v'=[5, 5, 7] otrzymamy tylko 38, a wartośc optymalna wynosi 20+12+11=43.

Problem plecakowy, w którym przedmioty są niepodzielne i zmuszeni jesteśmy albo zabrać dany przedmiot, albo też go odrzucić nazywany jest dyskretnym - problem w tej postaci nie poddaje się strategi zachłannej.
Jeśli odpowiednikami przedmiotów są np. substancje (ciecz, piasek), które można podzielić zabierając dowolną ich ilość, to problem plecakowy nazywamy ciągłym - w tej postaci algorytm zachłanny wybierający w pierwszej kolejności substancje o największej wartości jednostkowej prowadzi do optymalnego rozwiązania.

Jeśli ilość przedmiotów n i wartość b nie są zbyt duże możemy zadeklarować prostokatną tablicę wymiaru n x (b+1), której poszczególne wiersze związane będą z przedmiotami z1, z2, ..., zn, zaś kolumny z możliwymi do osiągnięcia objętościami przedmiotów w plecaku 1, 2, ..., b:

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
   --------------------------------------------------------
10| 0 x x x x x x x x x 20  x  x  x  x  x  x  x  x  x  x  x
7 |
5 |
5 |

Pierwszy wiersz tablicy zawiera informację o tym jaką objętość plecaka można zająć umieszczając z nim pierwszy z przedmiotów (D[1, 10]<>0) oraz jaka wówczas będzie wartość plecaka (D[1, 10]=20).
Nie jest to wcale oczywiste, że optymalne zapakowanie plecaka zawiera ten przedmiot, dlatego też zaznaczamy tu dodatkowo druga możliwość - jeśli pominiemy ten przedmiot, to plecak pozostanie pusty (D[1, 0]<>x) i ty samym jego wartość będzie równa zero (D[1, 0]=0).

Do plecaka zapakowanego ewentualnie tym jednym przedmiotem dokładamy drugi z listy przedmiot o objętości 7 i wartości 15. Dokładamy lub nie. Mamy tu cztery możliwości:

  • jeśli pominiemy ten przedmiot i pomineliśmy również przedmiot pierwszy, to komórka D[2, 0] powinna zawierać wartość 0

  • jeśli pominiemy ten przedmiot, a wcześniej zapakowaliśmy przedmiot pierwszy o pojemności 10, to komórka D[2, 10] powinna zawierać wartość plecaka 20

  • jeśli zapakujemy przedmiot drugi, a wcześniej pominęliśmy pzredmiot pierwszy, to komórka D[2, 7] powinna zawierać wartość 15

  • jeśli zapakujemy przedmiot drugi i wcześniej zapakowaliśmy przedmiot pierwszy, to komórka D[2, 17] powinna zawierać wartość plecaka 35

Po dołożeniu (lub niedołożeniu) drugiego przedmiotu tablica wygląda następująco:

    0 1 2 3 4 5 6  7 8 9 10 11 12 13 14 15 16  17 18 19 20 21
   ----------------------------------------------------------
10| 0 x x x x x x  x x x 20  x  x  x  x  x  x   x  x  x  x  x
7 | 0 x x x x x x 15 x x 20  x  x  x  x  x  x  35  x  x  x  x
5 |
5 |

Po zapakowaniu dwóch przedmiotów 10 i 7 maksymalna wartość plecaka wynosi 35 - pojemność ładunku jest wówczas równa 17.

Dokładając trzeci przedmiot o objętości 5 i wartości 11 możemy powiedzieć tak: jeśli została osiągnięta pewna objętość przedmiotów w plecaku np. 10, to dołożenie tego przedmiotu spowoduje, że zostanie również osiągnięta objętość 10+5=15 - wówczas wartość przedmiotów będzie równa 31.
Ogólnie: jeśli została osiągnięta pewna objętość przedmiotów w plecaku j, dla której wartość przedmiotów wynosiła D[2, j], to dokładając przedmiot kolejny 3 o objętości v[3] i wartości w[3], osiągniemy objętość przedmiotów j+v[3], których wartość będzie wówczas równa D[2, j]+w[3].

{Pola x w programie oznaczone beda jako -1}
For j:=0 To b Do
  Begin
    {Objetosc j jesli byla osiagalna z dwoch przedmiotow to pomijajac}
    { przedmiot trzeci pozostanie osiagalna nadal                    }
    D[3, j]:=D[2, j];
    {Byc moze dolozenie przedmiotu (o ile to mozliwe) jest bardziej  }
    {oplacalne                                                       }
    If j>=v[3] Then
      If (D[2, j-v[3]]<>-1) And (D[2, j-v[3]]+w[3]>D[3, j]) Then
        D[3, j]:=D[2, j-v[3]]+w[3];
  End;
    
    0 1 2 3 4  5 6  7 8 9 10 11 12 13 14 15 16  17 18 19 20 21
   -----------------------------------------------------------
10| 0 x x x x  x x  x x x 20  x  x  x  x  x  x   x  x  x  x  x
7 | 0 x x x x  x x 15 x x 20  x  x  x  x  x  x  35  x  x  x  x
5 | 0 x x x x 11 x 15 x x 20  x 26  x  x 31  x  35  x  x  x  x 
5 |

{Pola x w programie oznaczone beda jako -1}
For j:=0 To b Do
  Begin
    {Objetosc j jesli byla osiagalna z trzech przedmiotow to pomijajac}
    { przedmiot czwarty pozostanie osiagalna nadal                    }
    D[4, j]:=D[3, j];
    {Byc moze dolozenie przedmiotu (o ile to mozliwe) jest bardziej   }
    {oplacalne                                                        }
    If j>=v[4] Then
      If (D[3, j-v[4]]<>-1) And (D[3, j-v[4]]+w[4]>D[4, j]) Then
        D[4, j]:=D[3, j-v[4]]+w[4];
  End;

    0 1 2 3 4  5 6  7 8 9 10 11 12 13 14 15 16  17 18 19  20 21
   ------------------------------------------------------------
10| 0 x x x x  x x  x x x 20  x  x  x  x  x  x   x  x  x   x  x
7 | 0 x x x x  x x 15 x x 20  x  x  x  x  x  x  35  x  x   x  x
5 | 0 x x x x 11 x 15 x x 20  x 26  x  x 31  x  35  x  x   x  x 
5 | 0 x x x x 12 x 15 x x 23  x 27  x  x 32  x  38  x  x  43  x

Dokładając jeszcze jeden zerowy wiersz do tablicy D i inicjując komórkę D[0, 0]:=0, zaś pozostałe komórki zerowego wiersza wartością wskazującą na nieosiągalność danej objętości (-1) otrzymamy algorytm pakowania plecaka:

Const
  b = 21;
  n =  4;
Var
  w : Array[1..n] Of Integer;
  v : Array[1..n] Of Integer;
  i, j : Integer;
  D : Array[0..n, 0..b] Of Integer;
Begin
  v[1]:=10;
  v[2]:=7;
  v[3]:=5;
  v[4]:=5;
  w[1]:=20;
  w[2]:=15;
  w[3]:=11;
  w[4]:=12;


  D[0, 0]:=0;
  For j:=1 To b Do D[0, j]:=-1;

  {Wygeneruj tablice D}
  For i:=1 To n Do
    For j:=0 To b Do
      Begin
        D[i, j]:=D[i-1, j];
        If j>=v[i] Then
          If (D[i-1, j-v[i]]<>-1) And (D[i-1, j-v[i]]+w[i]>D[i, j]) Then
            D[i, j]:=D[i-1, j-v[i]]+w[i];
      End;

  {Wypisz tablice D}
  For i:=0 To n Do
    Begin
      For j:=0 To b Do Write(D[i, j]:3);
      WriteLn;
    End;

  {Wypisz maksymalna wartosc zaladunku}
  j:=0;
  For i:=1 To b Do
    If D[n, i]>D[n, j] Then j:=i;
  WriteLn('Maksymalna wartość załadunku = ', D[n, j]);
  ReadLn;
End.

Złożoność obliczeniowa: O(n*b).

Dokładając do plecaka przedmiot i o objętości v[i] sprawdzamy kolejno osiągalność wszystkich objętości: sprawdzając objętości j patrzymy jedynie na komórkę D[i-1, j-v[i]] w wierszu poprzednim. Do wygenerowania i-tego wiersza tablicy D nie są potrzebne wiersze wygenerowane wcześniej - potrzebujemy tylko wiersza poprzedniego i-1. Pozwala to na wykonanie algorytmu na tablicy jednowierszowej D[0..b].

Jest tylko drobny szczegół. Odwołanie D[i-1, j-v[j]] jak dotąd było odwołaniem do poprzedniego wiersza, teraz będzie to odwołanie do tego samego wiersza D[j-v[i]]. Może się więc zdarzyć, że w pętli For dla na przykład v[i]=5 zmienimy wartość komórki D[7]. Kilka kroków dalej, dla j=12 nastąpi odwołanie do komórki D[12-5]=D[7] i zmienimy również komórkę D[12] (a potem kolejno co 5: D[17], D[22], ...). Tą niedogodność rozwiąże pętla wykonywana z góry do dołu, od maksymalnej wartości b do wartości minimalnej 0:

D[0]:=0;
For j:=1 To b Do D[j]:=-1;

{Wygeneruj tablice D}
For i:=1 To n Do
  For j:=b DownTo 0 Do
    If j>=v[i] Then
      If (D[j-v[i]]<>-1) And (D[j-v[i]]+w[i]>D[j]) Then
        D[j]:=D[j-v[i]]+w[i];