Problem plecakowy — optymalizacja

Co się właśnie stało?

Mamy trzy przedmioty — A (waga 3, wartość 5), B (waga 2, wartość 3) i C (waga 2, wartość 3) — oraz plecak o pojemności $W=4$. Strategia zachłanna sięga po najcenniejszy przedmiot A (wartość 5), ale zajmuje on 3 z 4 jednostek wagi i nie starcza już miejsca na nic więcej. Tymczasem rezygnacja z A na rzecz dwóch tańszych przedmiotów B + C daje wartość 6 przy dokładnie zapełnionym plecaku (waga 4).

Problem plecakowy — na czym polega?

To klasyczny problem optymalizacji kombinatorycznej: mając przedmioty o wagach $w_i$ i wartościach $v_i$ oraz plecak o pojemności $W$, wybieramy podzbiór o maksymalnej łącznej wartości, który się w nim mieści:

Ograniczenie $\sum_i w_i \le W$ jest twarde — łączna waga wybranych przedmiotów nigdy nie może przekroczyć pojemności. Kusi, by rozwiązać zadanie „zachłannie" (brać zawsze najcenniejszy albo najlepszy lokalnie przedmiot o największym stosunku $v_i/w_i$), ale — jak widać powyżej — ta strategia nie gwarantuje optimum.

Dlaczego to trudne? Klasa NP i „P vs NP"

Znalezienie gwarantowanego rozwiązania optymalnego wymaga rozważenia wielu kombinacji przedmiotów, a liczba wszystkich podzbiorów $2^n$ rośnie wykładniczo z liczbą przedmiotów: dla 3 przedmiotów to 8 podzbiorów, dla 20 już ponad milion, dla 50 — więcej niż liczba atomów w wielu galaktykach. Dlatego problem plecakowy należy do klasy problemów NP-trudnych, ściśle związanej z jednym z najważniejszych nierozwiązanych pytań matematyki i informatyki: „P kontra NP". Jest ono jednym z 7 Problemów Milenijnych Instytutu Matematycznego Claya (2000 r.), a za jego rozwiązanie czeka nagroda 1 mln USD.

Gdzie to spotkasz w praktyce?

Problem plecakowy ma ogromne zastosowania: pakowanie ładunku o ograniczonej masie, budżetowanie inwestycji (które projekty sfinansować przy stałym budżecie?), alokacja zasobów, a nawet kryptografia. Pokazuje, że pozornie proste zadanie — „co spakować, żeby zabrać jak najwięcej wartości?" — może być obliczeniowo bardzo trudne.

Po co Ci to na maturze:

To modelowy przykład, że strategia zachłanna nie zawsze jest optymalna — intuicja „bierz najlepsze teraz" bywa zwodnicza. Ta sama ostrożność przydaje się w zadaniach o optymalizacji, kombinatoryce i rachunku prawdopodobieństwa: zanim uznasz lokalnie najlepszy ruch za globalnie najlepszy, sprawdź kontrprzykład.

Zapamiętaj: w problemie plecakowym suma wag wybranych przedmiotów musi spełniać $\sum_i w_i \le W$, a celem jest $\max \sum_i v_i$ — jednak strategia zachłanna nie gwarantuje maksymalnej wartości. Gwarancję daje dopiero przegląd kombinacji, którego koszt rośnie wykładniczo. To dlatego problem plecakowy jest NP-trudny, a pytanie „P kontra NP" wciąż czeka na odpowiedź.