Problem plecakowy

Dyskretny problem plecakowy

Dyskretny problem plecakowy (ang. discrete knapsack problem) to klasyczny problem optymalizacyjny, polegający na wyborze przedmiotów o określonej wadze i wartości, aby zmaksymalizować sumę wartości przy jednoczesnym ograniczeniu całkowitej wagi do pojemności plecaka.

W kontekście problemu, wyobrażamy sobie złodzieja, który ma do dyspozycji N towarów, gdzie każdy przedmiot ma przypisaną wartość $c\_j$ oraz wagę $w\_j$. Celem jest maksymalizacja wartości łupu, nie przekraczając wagi B.

Definicje problemu

Problem plecakowy można rozróżnić na kilka typów:

• Dyskretny problem plecakowy (0-1 knapsack problem): Maksymalizacja $\backslash sum\_\{j=1\}^N\; c\_j\; x\_j$ przy warunkach: $\backslash sum\_\{j=1\}^N\; w\_j\; x\_j\; \backslash leqslant\; B$, gdzie $x\_j\; =\; 0\; \backslash ;\; lub\; \backslash ;\; 1$.
• Ograniczony problem plecakowy (bounded knapsack problem): Podobny do dyskretnego, ale z ograniczeniem liczby przedmiotów $0\; \backslash leqslant\; x\_j\; \backslash leqslant\; b\_j$.
• Nieograniczony problem plecakowy (unbounded knapsack problem): Przypadek, w którym można użyć wielu egzemplarzy tych samych przedmiotów.
• Ciągły problem plecakowy: Umożliwia przyjmowanie ułamkowych części przedmiotów.

Algorytmy rozwiązujące problem plecakowy

Problem plecakowy można rozwiązać różnymi metodami, w tym:

1. Przegląd zupełny

Metoda brutalna, która sprawdza wszystkie możliwe kombinacje przedmiotów, mająca złożoność $\backslash Theta(2^n)$. Choć jest optymalna, nie jest efektywna dla dużych zbiorów danych.

2. Programowanie dynamiczne

Umożliwia rozwiązanie problemu w czasie pseudowielomianowym. Dla przypadku, gdzie przedmioty można powtarzać, algorytm rekurencyjny jest zdefiniowany jako:

• $A(0)\; =\; 0$
• $A(i)\; =\; \backslash max\; \backslash \{c\_j\; +\; A(i\; –\; w\_j)\; \backslash colon\; w\_j\; \backslash leqslant\; i\backslash \}$

Złożoność wynosi $\backslash Theta(nW)$.

3. Algorytm aproksymacyjny

Metoda zachłanna, która sortuje przedmioty według wartości do wagi i dodaje je do plecaka, aż do osiągnięcia maksymalnej pojemności. Osiąga wyniki nie gorsze niż $k/2$, gdzie $k$ to maksymalna wartość.

Złożoność algorytmu wynika głównie z sortowania i wynosi $\backslash Theta(n\; \backslash cdot\; \backslash log\{n\})$.

Ciągły problem plecakowy

Można go rozwiązać podobnie jak dyskretny problem, obliczając stosunek wartości do wagi i dodając elementy do plecaka, dopóki ich suma wag nie przekroczy pojemności.

Podsumowanie

Dyskretny problem plecakowy stanowi istotny temat w teorii obliczeń i kryptografii, a jego różnorodne wersje i algorytmy rozwiązujące są przedmiotem intensywnych badań. Problem plecakowy jest NP-zupełny, co czyni go trudnym do rozwiązania w czasie wielomianowym.