Problem Plecakowy

Beata Laszkiewicz

Brudnopis
Mamy danych $n$ przedmiotów, każdy o ustalonej wartości $p_i >0$, $(i=1, \ldots, n)$ oraz o ustalonej wadze $w_i >0$, $(i=1, \ldots, n)$ oraz plecak, który może pomieścić $W$ kilogramów, $W \geq 0$. Naszym zadaniem jest wybrać pewną liczbę przedmiotów tak, by w plecaku pozostało jak najmniej wolnego miejsca oraz by jego wartość była jak największa. Inaczej mówiąc, chcemy znaleźć wartości $q_1, q_2, \ldots, q_n \geq 0$, $q_i \in \mathbb C \quad (i=1, \ldots n)$ , dla których wartość plecaka

$P= p_1\cdot q_1+p_2 \cdot q_2+ \ldots + p_n \cdot q_n$

będzie największa oraz nie przekroczymy pojemności plecaka:

$w_1 \cdot q_1 + w_2 \cdot q_2 + \ldots w_n \cdot q_n \leq W$.

Istnieją dwie wersje tego problemu. Możemy założyć, że dysponujemy nieograniczoną ilością każdej z rzeczy, wtedy mówimy o ogólnym problemie plecakowym. Jeżeli każdy przedmiot występuje jeden raz, to mówimy o decyzyjnym problemie plecakowym.

W życiu codziennym podczas pakowania plecaka stosujemy najczęściej jedną z trzech strategii:

  • Strategia I: wybieramy najcenniejsze przedmioty (czyli w kolejności nierosnących wartości $p_i$),
  • Strategia II: wybieramy rzeczy zajmujące najmniej miejsca (czyli w kolejności niemalejących wag $w_i$),
  • Strategia III: wybieramy rzeczy najcenniejsze w stosunku do swojej wagi, czyli w kolejności nierosnących ilorazów $\frac{p_i}{w_i}$.

Wszystkie powyższe strategie opierają się na działaniu zachłannym, jednak takie podejście nie zawsze gwarantuje otrzymanie optymalnego rozwiązania.

Przykład (por. M. M. Sysło, Algorytmy, WSiP 1997)
Niech $W=23$, $n=4$, wartości i wagi przedmiotów przedstawiono w tabeli:

$i$ $1$ $2$ $3$ $4$
$p_i$ $2$ $5$ $7$ $10$
$w_i$ $1$ $3$ $2$ $3$
$\frac{p_i}{w_i}$ 2 $1\frac{2}{3}$ $3\frac{1}{2}$ $3\frac{1}{3}$

W przypadku strategii I wybieramy 7 przedmiotów nr 4 (7 * 3 = 21 kg) oraz 1 przedmiot nr 3 (2 kg), co daje $P=77$. Strategia II pozwala zapakować 23 przedmioty nr 1 (23 *1 = 23 kg), co daje wartość plecaka $P=46$. Stosując strategię III wybieramy 11 przedmiotów nr 3 (11 * 2 = 22 kg) oraz przedmiot nr 1 (1 kg). Wartość plecaka w tym przypadku jest równa $P=79$.

Patrząc na powyższy przykład można zauważyć, że zastosowanie strategii III nie daje optymalnego rozwiązania - można zapakować plecak tak, aby jego wartość była równa 80. Metoda programowania dynamicznego pozwoli znaleźć właśnie to rozwiązanie. W tej metodzie rozwiązujemy wszystkie mniejsze podproblemy. W przypadku problemu plecakowego oryginalny problem można zredukować na dwa sposoby:

  • zmniejszamy zestaw przedmiotów ( patrzymy tylko na przedmioty $1, 2, \ldots i$ dla $i \leq n$
  • zmniejszamy pojemność plecaka (do $j \leq W$).

CDN…


Rozwiązania wszystkich podproblemów możemy w prosty sposób zapamiętać w tablicy dwuwymiarowej.

Dane:
n - liczba przedmiotów
p[1..n] - tablica wartości kolejnych przedmiotów
w[1..n] - tablica wag kolejnych przedmiotów
W - maksymalna pojemność plecaka (W jednostek)

Wynik:
P[0..n][0..W] - tablica najlepszych "upakowań" plecaka

for (j=0; j<=W; j++) 
    P[0][j]=0;

for (i=0; i<=n; i++)
    P[i][0]=0;

for (i=1, i<=n; i++)
    for(j=1; j<=W; j++)
        if (j>w[i] && P[i-1][j]<P[i][j-w[i]]+p[i])
            P[i][j]=P[i][j-w[i]]+p[i];
        else
            P[i][j]=P[i-1][j];
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License