Problem plecakowy

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

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.

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

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

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

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 ilości 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

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

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

  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), 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

Media użyte na tej stronie

Knapsack greedy.svg
Autor: unknown, Licencja: CC BY-SA 2.5
Knapsack.svg
Autor: unknown, Licencja: CC BY-SA 2.5