Problem plecakowy

Z Wikipedii

Dyskretny problem plecakowy (ang. binary knapsack problem) jest jednym z najczęściej poruszanych problemów optymalizacyjnych. Formułuje się go następująco: mamy do dys­pozycji plecak o maksymalnej pojemności B oraz zbiór N elementów {x₁, x_j, ..., x_N}, przy czym każdy element ma określoną wartość c_j oraz wielkość w_j. Naszym zadaniem jest znalezienie takiego upakowania plecaka, aby suma wartości znajdujących się w nim elementów była jak największa. 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).

[edytuj] Realizacja algorytmu

Dyskretny problem plecakowy jest zagadnieniem NP-trudnym, nie znamy więc wielomianowego algorytmu znalezienia optymalnego upakowania. Istnieje kilka sposobów rozwiązania:

• Przegląd zupełny (bruteforce, metoda siłowa)– zdecydowanie najgorszy sposób; w jego przypadku złożoność obliczeniowa al­gorytmu wyniesie Θ(2ⁿ), co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi Θ(2ⁿ) ponieważ jest tyle możliwych ciągów zero jedynkowych na n polach. Złożoność można również wyliczyć ze wzoru dwumianowego Newtona (dwumian Newtona) podstawiając za a i b jedynki.
• Programowanie dynamiczne – można nazwać je rozszerzeniem metody "dziel i zwyciężaj". Problem rozwiązywany poprzez programowanie dynamiczne dzielony jest na szereg prostych do rozwiązania podproblemów, ale z uwzględnieniem dodatkowego warunku, że wyniki każdego wcześniej rozwiązanego podproblemu mogą zostać wy­korzystane do późniejszego rozwiązania innych podproblemów.

Ciągły problem plecakowy można rozwiązać za pomocą algorytmu zachłannego:

• Obliczyć dla każdego elementu stosunek wartości do wagi h_j = c_j/w_j, uszeregować uzyskane wartości od największej do najmniejszej (można to zrobić w czasie O(n*logn) ), a następnie wstawiać kolejne elementy do plecaka dopóki Σ w_j < B. Nie można w ten sposób rozwiązać problemu dyskretnego.