Problem plecakowy
Turystka z limitem wagi, złodziej z workiem, firma z budżetem i listą projektów: wszyscy stają przed tym samym pytaniem. Co zabrać, aby uzyskać jak największą wartość bez przekroczenia limitu? To problem plecakowy, a programowanie dynamiczne rozwiązuje go dokładnie, gdy wagi są liczbami całkowitymi umiarkowanej wielkości.
Problem
Jest n przedmiotów, każdy z wagą i wartością, oraz plecak, który mieści co najwyżej wagę W. Wybierz zbiór przedmiotów o łącznej wadze co najwyżej W i jak największej łącznej wartości. Każdy przedmiot trafia do plecaka w całości albo zostaje na zewnątrz, dlatego mówi się o problemie plecakowym 0/1. Przy n przedmiotach jest 2ⁿ możliwych zbiorów, więc sprawdzenie wszystkich szybko staje się niemożliwe.
Tabela
Niech best[i][w] oznacza największą wartość, która mieści się w wadze w przy użyciu tylko pierwszych i przedmiotów. Wtedy best[0][w] = 0, a dla każdego kolejnego wiersza są dwa wybory: pominąć przedmiot i, co daje best[i − 1][w], albo, jeśli jego waga wᵢ się mieści, spakować go, co daje jego wartość plus best[i − 1][w − wᵢ]. Większa z nich to best[i][w]. Gdy wypełnia się tabelę wiersz po wierszu, obie potrzebne komórki są zawsze gotowe.
Przykład
Weź pojemność 7 i cztery przedmioty o wagach 1, 3, 4 i 5 oraz wartościach 1, 4, 5 i 7. Z samym pierwszym przedmiotem każda pojemność od 1 wzwyż jest warta 1. Po dodaniu drugiego pojemność 4 mieści oba za 5. Po dodaniu trzeciego pojemność 7 mieści przedmioty 2 i 3 za 9. Czwarty przedmiot, o wadze 5 i wartości 7, mógłby dołączyć do przedmiotu 1 za 8 przy pojemności 6 lub 7, ale 9 jest lepsze, więc prawa dolna komórka to 9: spakuj przedmioty o wagach 3 i 4.
Jak trudny jest ten problem?
Tabela wymaga około n·W kroków. Wygląda to na szybkie, ale W jest liczbą, a liczba o d cyfrach może być tak duża jak 10 do potęgi d, więc praca rośnie wykładniczo z długością danych wejściowych. Problem plecakowy jest NP-trudny; był jednym z 21 problemów NP-zupełnych, które w 1972 roku opisał Richard Karp. W praktyce tabela, metoda podziału i ograniczeń oraz dobre schematy aproksymacyjne dobrze radzą sobie z dużymi rzeczywistymi przypadkami.
Historia i zastosowania
Nazwę wprowadził na początku XX wieku matematyk Tobias Dantzig, a jego syn George Dantzig podał dla tego problemu klasyczną metodę zachłanną w 1957 roku. Problemy plecakowe pojawiają się przy planowaniu budżetu i wyborze portfela inwestycji, przy cięciu surowca z jak najmniejszymi odpadami, przy załadunku towarów, a nawet we wczesnej kryptografii klucza publicznego: kryptosystem Merkle–Hellman z 1978 roku opierał się na problemie plecakowym i został złamany kilka lat później.
Sprawdź to w praktyce
Otwórz aplikację, przejdź do widoku Tabela i naciśnij Krok. Pomarańczowa komórka jest właśnie wypełniana, a niebieskie komórki to dwie, które porównuje: komórka bezpośrednio powyżej oraz, w wierszu powyżej, komórka przesunięta o wagę przedmiotu w lewo. Po ostatniej komórce odczyt wstecz wspina się na pomarańczowo od prawego dolnego narożnika, a spakowane przedmioty pojawiają się pod tabelą.
Często zadawane pytania
Czym różnią się problem plecakowy 0/1, ograniczony i nieograniczony?
W wersji 0/1 każdy przedmiot bierze się co najwyżej raz. W wersji ograniczonej każdy przedmiot ma ograniczoną liczbę egzemplarzy, a w nieograniczonej dowolną. Tabela zmienia się między nimi tylko nieznacznie.
Czy metoda zachłanna jest kiedyś dobra dla problemu plecakowego?
W ciągłym problemie plecakowym, w którym przedmioty można dzielić, branie najpierw najlepszej wartości na jednostkę wagi jest optymalne. Przy całych przedmiotach może być daleka od optimum, choć lepsze z rozwiązania zachłannego i pojedynczego najcenniejszego przedmiotu jest zawsze warte co najmniej połowę najlepszej wartości.
Ile pamięci potrzebuje tabela?
(n + 1)·(W + 1) komórek dla pełnej tabeli, której potrzeba, aby odczytać przedmioty wstecz. Jeśli potrzebna jest tylko najlepsza wartość, wystarczy jeden wiersz z W + 1 komórkami, wypełniany od prawej do lewej.
Czy problem plecakowy to to samo co problem sumy podzbioru?
Problem sumy podzbioru to szczególny przypadek, w którym wartość każdego przedmiotu jest równa jego wadze, a pytanie brzmi, czy plecak da się wypełnić dokładnie. On również jest NP-zupełny i rozwiązuje się go tym samym rodzajem tabeli.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj problem plecakowy