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 oraz waży 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 może być osiągnięta bez przekraczania wagi ?”.

Definicja

edytuj

Definicja formalna: mamy do dyspozycji plecak o maksymalnej pojemności   oraz zbiór   elementów   przy czym każdy element ma określoną wartość   oraz wielkość  

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

formalnie problem może być zdefiniowany:
zmaksymalizuj  
przy założeniach:  

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

Formalnie:
zmaksymalizuj  
przy założeniach:  

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  

utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie  ? 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

edytuj

Przegląd zupełny

edytuj

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   co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi   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

edytuj

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   będą wagami poszczególnych elementów oraz   ich wartościami. Algorytm ma zmaksymalizować sumę wartości elementów przy zachowaniu sumy ich wagi mniejszej bądź równej   Niech   będzie największą możliwą wartością, która może być otrzymana przy założeniu wagi mniejszej bądź równej     jest rozwiązaniem problemu.

  jest zdefiniowane rekurencyjnie:

  •  
  •  

Rozwiązanie dla pustego plecaka jest równe zero. Obliczenie wyników kolejno dla   aż do   pozwala obliczyć wynik. Ponieważ obliczenie   wymaga sprawdzenia   elementów, a wartości   do obliczenia jest   złożoność obliczeniowa programu wynosi  

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

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   będzie wagą elementów oraz   wartościami. Algorytm ma zmaksymalizować wartość elementów przy zachowaniu sumy ich wagi mniejszej bądź równej   Niech   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 wykorzystaniu pierwszych   elementów.   jest rozwiązaniem problemu.

Funkcję   definiowana jest rekurencyjnie:

  •  
  •  
  •   jeśli  
  •   jeśli  

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

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

edytuj
 
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   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   jest maksymalną wartością przedmiotów w optymalnie upakowanym plecaku, algorytm zachłanny osiąga wyniki nie gorsze niż  [2]. Złożoność obliczeniowa algorytmu zależy od sortowania  

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

edytuj

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   uszeregować uzyskane wartości od największej do najmniejszej (można to zrobić w czasie  ), a następnie wstawiać kolejne elementy do plecaka dopóki  

Przypisy

edytuj
  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.
  2. a b Algorithms and Complexity (Freiburg) [online], www.informatik.uni-freiburg.de [dostęp 2017-11-26] (niem.).

Bibliografia

edytuj
  • 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

edytuj