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 {x1, xj, ..., xN}, przy czym każdy element ma określoną wartość cj oraz wielkość wj. 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 cj oraz waży wj. 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).

Realizacja algorytmu

Problem plecakowy jest zagadnieniem NP-trudnym, nie ma 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 Θ(2n), co zdecydowanie zawyży czas działania dla dużych n. Złożoność wynosi Θ(2n) 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.
  • Algorytmy przybliżone – można np. obliczyć dla każdego elementu stosunek wartości do wagi hj = cj/wj, uszeregować uzyskane wartości od największej do najmniejszej, a następnie wstawiać kolejne elementy do plecaka dopóki Σ wj < B. Oczywistą wadą takiego rozwiązania jest niepewność co do optymalności otrzymanego upakowania.
  • 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.
Publikacja wraz ze zdjęciami jest udostępniona w Encyklopedii "Zgapedia" części portalu zgapa.pl. Treść objęta jest licencją GNU FDL Wolnej Dokumentacji w wersji 1.3 lub dowolnej pózniejszej opublikowanej przez Free Software Foundation i została ona opracowana na podstawie Wikipedii, tutaj możesz znaleźć artykuł źródłowy oraz autorów. Warunki użytkowania Encyklopedii znajdziesz na tej stronie.