Problem plecakowy

Dyskretny problem plecakowy (ang. discrete knapsack problem) – jeden z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich wartość sumaryczna była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości należy wybrać taki podzbiór, by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.

Które pudełka powinny być wybrane, aby zmaksymalizować wartość przedmiotów w plecaku i jednocześnie nie zabrać więcej niż 15 kg?

Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j-ty przedmiot jest wart $c_{j}$ oraz waży $w_{j}.$ Złodziej dąży do zabrania ze sobą jak najwartościowszego łupu, przy czym nie może zabrać więcej niż B kilogramów. Nie może też zabierać ułamkowej części przedmiotów (byłoby to możliwe w ciągłym problemie plecakowym).

Podobny problem pojawia się często w kombinatoryce, teorii złożoności obliczeniowej, kryptografii oraz matematyce stosowanej.

Decyzyjna wersja przedstawionego zagadnienia to pytanie: „Czy wartość co najmniej $C$ może być osiągnięta bez przekraczania wagi $W$ ?”.

Definicja

Definicja formalna: mamy do dyspozycji plecak o maksymalnej pojemności $B$ oraz zbiór $N$ elementów $\{x_{1},x_{j},\dots ,x_{N}\},$ przy czym każdy element ma określoną wartość $c_{j}$ oraz wielkość $w_{j}.$

Dyskretny problem plecakowy (ang. 0-1 knapsack problem)

formalnie problem może być zdefiniowany:

zmaksymalizuj

\sum _{j=1}^{N}c_{j}x_{j}

przy założeniach:

\sum _{j=1}^{N}w_{j}x_{j}\leqslant B,\qquad x_{j}=0\;{\mbox{lub}}\;1,\quad j=1,\dots ,n.

Problem plecakowy, w którym liczba elementów danego typu jest ograniczona przez podaną wartość (ang. bounded knapsack problem).

Formalnie:

zmaksymalizuj

\sum _{j=1}^{N}c_{j}x_{j}

przy założeniach:

\sum _{j=1}^{N}w_{j}x_{j}\leqslant B,\qquad 0\leqslant x_{j}\leqslant b_{j},\quad j=1,\dots ,n.

Można rozważać także przypadek, w którym nie ma wartości ograniczającej liczbę elementów danego typu (ang. unbounded knapsack problem).

W ciągłym problemie plecakowym można brać ułamkowe części przedmiotów.

W przypadku, gdy problem jest rozważany przy założeniach, że

jest problemem decyzyjnym,
jest dyskretny,
dla każdego elementu waga równa się wartości $w_{j}=c_{j},$

utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie $W$ ? Zagadnienie to nazywane jest problemem sumy podzbioru.

Problem plecakowy może być rozwiązany przy użyciu programowania dynamicznego, ale rozwiązanie wielomianowe nie jest znane. Problem plecakowy oraz sumy podzbioru są problemami NP trudnymi, co było powodem użycia sumy podzbioru jako podstawy w niektórych systemach kryptografii asymetrycznej takich jak Merkle-Hellman. Algorytmy takie używały grup, nie liczb całkowitych. Merkle-Hellman oraz kilka podobnych algorytmów zostało w późniejszym czasie złamanych, ponieważ szczególny problem sumy podzbioru użyty w tych algorytmach był rozwiązywalny w czasie wielomianowym^[1].

Decyzyjna wersja problemu plecakowego opisana wyżej jest problemem NP zupełnym i jest jednym z 21 NP zupełnych problemów Karpa.

Realizacje algorytmu

Przegląd zupełny

Przegląd zupełny (bruteforce, metoda siłowa) – metoda nieefektywna obliczeniowo (ale optymalna, gdyż znajduje rozwiązanie najlepsze); w jego przypadku złożoność obliczeniowa algorytmu wyniesie $\Theta (2^{n}),$ co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi $\Theta (2^{n}),$ ponieważ jest tyle możliwych ciągów zero-jedynkowych na n polach. Złożoność można również obliczyć ze wzoru dwumianowego Newtona (dwumian Newtona), podstawiając za, a i b jedynki.

Rozwiązania dynamiczne

Problem plecakowy może być rozwiązany w czasie pseudowielomianowym przy użyciu programowania dynamicznego. Rozwiązanie podane poniżej dotyczy przypadku, w którym można użyć wielokrotnie każdego elementu:

Niech $w_{1},\dots ,w_{n}$ będą wagami poszczególnych elementów oraz $c_{1},\dots ,c_{n}$ ich wartościami. Algorytm ma zmaksymalizować sumę wartości elementów przy zachowaniu sumy ich wagi mniejszej bądź równej $W.$ Niech $A(i)$ będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej $i.$ $A(W)$ jest rozwiązaniem problemu.

$A(i)$ jest zdefiniowane rekurencyjnie:

$A(0)=0,$
$A(i)=\max\{c_{j}+A(i-w_{j})\colon w_{j}\leqslant i\}.$

Rozwiązanie dla pustego plecaka jest równe zero. Obliczenie wyników kolejno dla $A(0),A(1)\dots$ aż do $A(W)$ pozwala obliczyć wynik. Ponieważ obliczenie $A(i)$ wymaga sprawdzenia $n$ elementów, a wartości $A(i)$ do obliczenia jest $W,$ złożoność obliczeniowa programu wynosi $\Theta (nW).$

Powyższa złożoność nie neguje faktu, że problem plecakowy jest NP-zupełny, ponieważ $W,$ w przeciwieństwie do $n,$ nie jest proporcjonalne do rozmiaru danych wejściowych dla problemu. Rozmiar wejścia jest proporcjonalny do liczby bitów w liczbie $W,$ a nie do wartości $W.$

Pseudokod (rozwiązanie znajduje się w komórce A[W], tablica A[0..W] przechowuje wyniki, wagi znajdują się w tablicy w[1..n], a wartości w tablicy c[1..n]):

  for i:=0 to W do
    A[i]:= 0

  for i:=0 to W do
    for j:=1 to n do
      if ( w[j] <= i ) then //sprawdzenie czy j-ty element mieści się w plecaku o rozmiarze i
        A[i] = max(A[i], A[i-w[j]] + c[j])

Podobne rozwiązanie może zostać zastosowane dla dyskretnego problemu plecakowego, także działające w czasie pseudowielomianowym. Niech $w_{1},\dots ,w_{n}$ będzie wagą elementów oraz $c_{1},\dots ,c_{n}$ wartościami. Algorytm ma zmaksymalizować wartość elementów przy zachowaniu sumy ich wagi mniejszej bądź równej $W.$ Niech $A(i,j)$ będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej $j$ i wykorzystaniu pierwszych $i$ elementów. $A(n,W)$ jest rozwiązaniem problemu.

Funkcję $A(i,j)$ definiowana jest rekurencyjnie:

$A(0,j)=0,$
$A(i,0)=0,$
$A(i,j)=A(i-1,j),\quad {}$ jeśli $w_{i}>j,$
$A(i,j)=\max(A(i-1,j),c_{i}+A(i-1,j-w_{i}))\quad {}$ jeśli $w_{i}\leqslant j.$

Rozwiązaniem problemu jest wynik dla $A(n,W).$ Do efektywnego wykonania algorytmu używa się tablicy do zapamiętywania obliczonych podproblemów. Złożoność obliczenia wynosi podobnie jak wyżej $\Theta (nW),$ podobnie jak złożoność pamięciowa. Przy niewielkich modyfikacjach można jednak zredukować ilość potrzebnej pamięci do rzędu $\Theta (W).$

Pseudokod (tablica A[1..n,0..W] przechowuje wyniki, wagi znajdują się w tablicy w[1..n], a wartości w tablicy c[1..n], rozwiązanie znajduje się w komórce A[n,W]):

  for i:=0 to n do
    A[i,0]:= 0
  for j:=0 to W do
    A[0,j]:= 0

  for i:=1 to n do //rozważanie kolejno i pierwszych przedmiotów
    for j:=0 to W do
      if ( w[i] > j ) then //sprawdzenie czy i-ty element mieści się w plecaku o rozmiarze j
        A[i,j] = A[i-1,j]
      else
        A[i,j] =  max(A[i-1,j], A[i-1,j-w[i]] + c[i])

Algorytm aproksymacyjny

W pierwszej części algorytmu zachłannego przedmioty są sortowane według stosunku wartości do wagi (po lewej), po czym wybierane są kolejno od góry te elementy które się jeszcze mieszczą w plecaku. W wyniku wybrane zostały przedmioty o 1. i 3. o łącznej wartości 11$ i wadze 11 kg. Optymalnym wynikiem byłyby jednak przedmioty 1. i 5. o łącznej wadze 14 kg i wartości 12$.

W wersji zachłannej algorytm aproksymacyjny sortuje elementy w kolejności malejącej, porównując stosunek wartości do wagi elementu $h_{j}={\frac {c_{j}}{w_{j}}}.$ Następnie wstawia je kolejno, zaczynając od przedmiotu o największym ilorazie do plecaka. Jeśli jakiś element nie mieści się w plecaku, to jest omijany, a algorytm przechodzi do następnego. W algorytmie wybierany jest maksymalny wynik z tak obliczonego upakowania plecaka oraz plecaka z elementem o największej wartości. Jeśli $k$ jest maksymalną wartością przedmiotów w optymalnie upakowanym plecaku, algorytm zachłanny osiąga wyniki nie gorsze niż $k/2$ ^[2]. Złożoność obliczeniowa algorytmu zależy od sortowania $(\Theta (n\cdot \log {n})).$

Pseudokod:

posortuj nierosnąco przedmioty według wartości c[j]/w[j]
aktualna_waga:=0

for i:=1 to n do
  if w[i] + aktualna_waga <= W then
    dodaj i-ty przedmiot do plecaka
    aktualna_waga := aktualna_waga + w[i]

Po wykonaniu tej części algorytmu należy porównać wynik z plecakiem, w którym jest przedmiot o największej wartości^[2].

Po raz pierwszy zachłanny algorytm aproksymacyjny został zaproponowany przez George’a Dantziga w 1957 roku.

Ciągły problem plecakowy

Można go rozwiązać za pomocą algorytmu zachłannego, takiego samego jak w przypadku aproksymacyjnego algorytmu dla dyskretnego problemu plecakowego: obliczyć dla każdego elementu stosunek wartości do wagi $h_{j}={\frac {c_{j}}{w_{j}}},$ uszeregować uzyskane wartości od największej do najmniejszej (można to zrobić w czasie $\Theta (n\cdot \log {n})$ ), a następnie wstawiać kolejne elementy do plecaka dopóki $\sum w_{j}<B.$

Przypisy

↑ Knapsack Encryption Scheme Broken. math.ohio-state.edu. [zarchiwizowane z tego adresu (2007-11-22)]., « Math Matrix », Wydział matematyki Ohio State University, wiosna 1985, Vol. 1, No. 3.
↑ ^a ^b Algorithms and Complexity (Freiburg) [online], www.informatik.uni-freiburg.de [dostęp 2017-11-26] (niem.).

Bibliografia

Michael R. Garey, David J. Johnson: Computers and intractability: a guide to the theory of NP-completeness. San Francisco: W.H. Freeman, 1979. ISBN 0-7167-1045-5.
Silvano Martello, Paolo Toth: Knapsack problems: algorithms and computer implementations. Chichester: J. Wiley, 1990. ISBN 0-471-92420-2.
Hans Kellerer, Ulrich Pferschy, David Pisinger: Knapsack Problems. Springer. ISBN 3-540-40286-1.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2003. ISBN 83-204-2800-9.

Linki zewnętrzne

Wykład dotyczący problemu plecakowego

[1] Knapsack Encryption Scheme Broken. math.ohio-state.edu. [zarchiwizowane z tego adresu (2007-11-22)]., « Math Matrix », Wydział matematyki Ohio State University, wiosna 1985, Vol. 1, No. 3.

[uni-freiburg-2] Algorithms and Complexity (Freiburg) [online], www.informatik.uni-freiburg.de [dostęp 2017-11-26] (niem.).

[1]

[2]