0/1 Tornio i Programowanie Dynamiczne

Problem z pakowaniem bez skrótów

Masz plecak o pojemności W i n przedmiotów, każdy z wagą i wartością. Możesz wziąć każdy przedmiot w całości lub nie w ogóle – nie można dzielić przedmiotu na pół, stąd "0/1". Celem jest wybranie podzbioru przedmiotów, który maksymalizuje łączną wartość przy jednoczesnym utrzymaniu łącznej wagi poniżej W. Przy n przedmiotach istnieje 2^n możliwych podzbiorów i sprawdzenie wszystkich z nich jest możliwe tylko dla bardzo małych n. Programowanie dynamiczne przekształca tę wykładniczą poszukiwanie w coś znacznie tańszego, zauważając, że problem posiada nakładające się podproblemy.

Rekurencyjna występowanie take-vs-skip

Zdefiniuj dp[i][w] jako najlepszą wartość osiągniętą przy użyciu tylko pierwszych i elementów o budżecie pojemności w. Dla danego elementu i mając dwie możliwości, dp[i][w] jest lepszą z nich:

dp[0][w] = 0 dla wszystkich w (nie ma jeszcze elementów) dp[i][w] = dp[i-1][w] jeśli weight[i] > w (trzeba pominąć — za ciężki) dp[i][w] = max( dp[i-1][w], // pomin element i dp[i-1][w - weight[i]] + value[i] ) // pobierz element i w przeciwnym razie Każda komórka potrzebuje tylko wiersza bezpośrednio nad nią, więc całą tabelę można wypełnić wiersz po wierszu, od lewej do prawej, w czasie O(n·W), a jeśli potrzebujesz tylko ostatecznej wartości, możesz użyć O(W) pamięci, utrzymując pojedynczą rolującą linię (iterowaną od wysokiego w do niskiego w, więc każdy element jest używany tylko raz). Ostatnia komórka, dp[n][W], jest odpowiedzią.

dp[0][w] = 0                                    for all w   (no items yet)

dp[i][w] = dp[i-1][w]                            if weight[i] > w   (must skip — too heavy)

dp[i][w] = max( dp[i-1][w],                      // skip item i
                dp[i-1][w - weight[i]] + value[i] )  // take item i
                                                  otherwise

demo na żywo · powiązana symulacja● LIVE

Wykorzystywanie backtrackingu do odzyskania rzeczywistych przedmiotów

Tabela dostarcza optymalnej wartości, ale zazwyczaj chcemy również wiedzieć, które przedmioty należy spakować. Rozpoczynając od dp[n][W], porównujemy ją z dp[n-1][W]: jeśli są równe, przedmiot n nie był potrzebny, więc przechodzimy do dp[n-1][W] i powtarzamy; jeśli się różnią, przedmiot n musiał zostać zabrany, więc go rejestrujemy i przechodzimy do dp[n-1][W - waga[n]]. Powtarzanie tego aż do dp[0][0] rekonstruuje dokładnie jeden optymalny zestaw przedmiotów, w O(n) dodatkowych krokach po zbudowaniu tabeli.

Dlaczego strategia 'złagodzenia' zawodzi tutaj

Naturalnym skrótem jest posortowanie elementów według współczynnika wartości do wagi i żądanie najlepszego współczynnika, o ile nadal mieści się w dostępnej pojemności. Jest to udowodniona optymalność dla problemu torba frakcyjnego, gdzie elementy można dzielić — ale dla torba 0/1 może być dowolnie zła. Pojedynczy przykład pokazuje to wyraźnie: przy pojemności 10 i dwóch przedmiotów, jeden ważący 6 o wartości 6 (współczynnik 1.0) oraz drugi ważący 5 o wartości 5.5 oraz trzeci ważący 5 o wartości 5.5 (współczynnik 1.1 każdy), strategia 'złagodzenia' wybierze element z minimalnie gorszym współczynnikiem… podstawnym problemem jest zawsze to samo: strategia 'złagodzenia' wczesnie zobowiąże się do wyboru elementu, który wydaje się najlepszy w izolacji i może pozostawić pojemność nie wykorzystaną, której inny zestaw by użył całkowicie, podczas gdy rekurencja DP poprawnie porównuje każdą kombinację implikowanie poprzez swój dwuwyborowy rekurencyjny charakter.

Kiedy sama tabela staje się wąskim gardłem

Czas wykonania O(n·W) jest mylący: wydaje się, że jest to wielomianowy w zależności od rozmiaru wejścia, ale W jest liczbą, a dane wejściowe potrzebują tylko około log₂(W) bitów, aby je zakodować – algorytm jest pseudo-polinomem. Dla pojemności kilku tysięcy jest to natychmiastowe; dla pojemności na miliardy tabela staje się niemożliwie duża, nawet jeśli n jest małe. W prawdziwych zastosowaniach logistycznych i finansowych z ogromnymi pojemnościami lub ciągłymi wagami zamiast tego stosuje się algorytm branch-and-bound, meet-in-the-middle dla umiarkowanego n lub schematy przybliżone, które handlują niewielką, udowodnioną graniczną utratą optymalności w zamian za wykonalny czas wykonania.

Frequently asked questions

Dlaczego podejście żądne — zawsze wybieranie przedmiotu o najwyższym współczynniku wartości do wagi — zawodzi w przypadku plecaka 0/1?

Wynika to z faktu, że nie można brać ułamkowej części przedmiotu. Podejście żądne może wypełnić pojemność przedmiotem o wysokim współczynniku, pozostawiając niezręczną ilość wolnej przestrzeni, marnując przestrzeń, którą w pełni wykorzystałoby inne, nieco niższe współczynniki kombinacja. Działa to dla wersji plecaka z możliwością dzielenia przedmiotów, gdzie można je podzielić, ale nie dla 0/1.

Czy rozwiązanie dynamiczne dla plecaka 0/1 jest szybkie w ścisłym sensie?

Uruchamia się w czasie O(n·W), co wygląda na wielomianowe, ale nie jest, ponieważ W to liczba, a nie rozmiar wejścia – wejście potrzebuje tylko log(W) bitów do zapisania. Nazywa się to czasem pseudo-polinomowym i dlatego tabela DP staje się niewykonalnie duża, gdy pojemności wynoszą miliony, mimo że jest w pełni wykonalna dla typowych, małych pojemności spotykanych w przykładach edukacyjnych.

Jakie zmiany zachodzą, jeśli można brać wielokrotne kopie tego samego przedmiotu?

To problem plecaka nieograniczonego, a do rekurencji wystarczy jedna zmiana w jednym wierszu: podczas rozważania przedmiotu pozwalasz sobie na ponowne wykorzystywanie bieżącego wiersza zamiast tylko wiersza powyżej, ponieważ webranie jednej kopii nie zabrania webrania innej. Ograniczenie 0/1 znika i DP nadal działa w podobnym czasie pseudo-polinomowym.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz 0/1 Knapsack i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację 0/1 Knapsack

0/1 Tornio: Programowanie Dynamiczne, Komórka po Komórce