0/1 Rozwiązanie problemu z plecakiem przy użyciu przykładu programowania dynamicznego

Na czym polega problem z plecakiem?

Problem z plecakiem to klasyczny problem optymalizacji kombinatorycznej. Supermarket przechowuje n pakiety (n ≤ 100). Pakiet i ma ciężar W[i] ≤ 100 i wartość V[i] ≤ 100. Złodziej nie może przenosić ciężaru przekraczającego ładowność M (M ≤ 100). Które paczki powinien zabrać złodziej, aby zmaksymalizować całkowitą wartość?

Wejście:

• Maksymalna waga M i liczba paczek n.
• Tablica wag W[i] i odpowiadająca im wartość V[i].

Wyjście:

• Maksymalna łączna wartość możliwa do uzyskania w ramach pojemności.
• Dokładny zestaw paczek, które złodziej powinien zabrać.

Algorytm plecakowy dzieli się na dwie dobrze znane odmiany:

• 0/1 Problem z plecakiem rozwiązane za pomocą programowania dynamicznego. Każdy pakiet jest albo pobierany w całości, albo pomijany — bez ułamkowych części i duplikatów.
• Problem ułamkowego plecaka Rozwiązaniem jest strategia zachłanności. W tym przypadku możesz wziąć ułamek dowolnego pakietu, aby wypełnić pozostałą pojemność.

Jak rozwiązać problem plecakowy za pomocą programowania dynamicznego na przykładzie

Metoda „dziel i zwyciężaj” dzieli duży problem na podproblemy, a następnie kontynuuje dzielenie, aż każdy podproblem stanie się łatwy. Zwykła rekurencja często jednak rozwiązuje ten sam podproblem wielokrotnie i marnuje pracę.

Główną ideą programowania dynamicznego plecakowego jest przechowywanie każdego rozwiązanego podproblemu w tabeli. Powtarzane wywołania odczytują odpowiedź zamiast ją przeliczać, przekształcając rekurencję wykładniczą w kod wielomianowy.

Rozwiąż problem plecakowy za pomocą programowania dynamicznego

Aby zaprojektować rozwiązanie w oparciu o programowanie dynamiczne, należy wykonać cztery kroki:

• Najpierw rozwiązuj najmniejsze podproblemy.
• Wyprowadź rekurencję, która zbuduje odpowiedź na podproblem na podstawie mniejszych problemów.
• Przechowuj odpowiedzi na podproblemy w tabeli obliczonej od dołu do góry, korzystając z rekurencji.
• Zbierz ostateczną odpowiedź z całkowicie wypełnionej tabeli.

Przeanalizuj problem plecakowy 0/1

Optymalna wartość zależy od dwóch niezależnych czynników:

1. Ile pakietów jest nadal rozpatrywanych?
2. Pozostałą wagę można jeszcze pomieścić w plecaku.

Ponieważ funkcja celu zależy od dwóch wielkości, tabela opcji musi być dwuwymiarowa. Niech B[i][j] oznaczają wartość maksymalną przy wyborze spośród opakowań {1, …, i} o limicie wagowym j.

• Ostateczna odpowiedź brzmi B[n][M], najlepsza łączna wartość spośród wszystkich n pakietów o pojemności M.
• Całkowita wybrana waga jest zawsze ograniczona przez aktualną ładowność: B[i][j] ≤ j.

Przykład: jeśli B[4][10] = 8, najlepsza całkowita waga pierwszych czterech paczek o ładowności 10 wynosi 8. Niektóre z tych czterech paczek można pominąć.

Wzór do obliczenia B[i][j]

• W[i], V[i] to waga i wartość paczki i, gdzie i jest w {1, …, n}.
• M jest maksymalną wagą, jaką plecak może udźwignąć.

Przypadek bazowy z jednym pakietem: dla każdej pojemności j ≥ W[1]:

B[1][j] = W[1]

W przypadku ogólnym zdecyduj, czy uwzględnić pakiet i w ramach pojemności j:

• Jeśli pakiet i jest pominięte, B[i][j] równa się najlepszej wartości przy użyciu pakietów {1, …, i-1} przy pojemności j:

B[i][j] = B[i - 1][j]

• Jeśli pakiet i jest Zadania (dozwolone tylko wtedy, gdy W[i] ≤ j), B[i][j] równa się V[i] plus najlepsza wartość z pakietów {1, …, i-1} przy pojemności j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

Wybierz większego z tych dwóch kandydatów.

Podstawy programowania dynamicznego

Połączenie tych dwóch przypadków daje pełną rekurencję:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

Podstawowym przypadkiem jest B[0][j] = 0 dla każdego j, ponieważ zero pakietów daje zerową wartość niezależnie od pojemności.

Oblicz tabelę opcji

Zbuduj B, używając rekurencji. Po wypełnieniu B ta sama tabela steruje trace-back, który rekonstruuje wybrane pakiety. Tabela B ma n + 1 wierszy i M + 1 kolumn:

• Wiersz 0 jest przypadkiem bazowym, wypełnionym zerami.
• Użyj wiersza 0, aby obliczyć wiersz 1, wiersza 1, aby obliczyć wiersz 2 i kontynuuj, aż wiersz n zostanie ukończony.

Tabela opcji

Trace

Po ukończeniu B skup się na B[n][M], optymalna wartość całkowita dla wszystkich n pakietów o pojemności M.

• If B[n][M] = B[n-1][M], pakiet n nie został wybrany, więc kontynuuj tracz B[n-1][M].
• If B[n][M] ≠ B[n-1][M]wybrano pakiet n, więc kontynuuj tracz B[n-1][M – W[n]].

Powtarzaj, aż dojdziesz do wiersza 0 tabeli.

Algorytm przeglądania tabeli opcji w celu znalezienia wybranych pakietów

Uwaga: kiedykolwiek B[i][j] = B[i-1][j], pakiet i nie jest wybrany. Wartość B[n][M] jest optymalną całkowitą wartością spakowaną do plecaka.

Kroki dla tracw wybranych pakietach:

• Krok 1: Zacznij od i = n, j = M.
• Krok 2: Przeskanuj kolumnę j od dołu do góry, aż znajdziesz wiersz i, gdzie B[i][j] > B[i-1][j]. Zaznacz pakiet i jako wybrany: Select[i] = true.
• Krok 3: Zaktualizuj j = j – W[i]. Jeśli j > 0, wróć do kroku 2, w przeciwnym razie przejdź do kroku 4.
• Krok 4: Wydrukuj wszystkie pakiety oznaczone jako wybrane.

Java Code

Poniższy Java metoda wypełnia B[][] od dołu, drukuje tabelę do inspekcji, a następnie tracto wybrane pakiety.

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Funkcja plecakDyProg() w Java

Wyjaśnienie kodu:

1. Przydziel tabelę B[][] i zainicjuj każdą komórkę wartością 0.
2. Wypełnij B[][] od dołu do góry, korzystając z rekurencji z poprzedniej sekcji.
3. Rozpocznij każdą komórkę wartością „pomiń pakiet i” B[i-1][j].
4. Jeżeli wybranie pakietu i jest wykonalne i daje zdecydowanie lepszą wartość, nadpisz komórkę.
5. TracPrzenieś wybrane elementy z wiersza n z powrotem do wiersza 0.
6. Za każdym razem, gdy wybrany zostanie pakiet n, zmniejsz pozostałą pojemność o W[n-1].

Poprawka: oryginalny fragment kodu zmutował parametr M podczas czytania B[n][M]. Bezpieczniejsza wersja powyżej wykorzystuje oddzielny kursor j dla trace.

Java Sterownik uruchamia algorytm na dwóch przykładach:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Dane wyjściowe pierwszego przykładu:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

Dane wyjściowe drugiego przykładu:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Złożoność czasowa i przestrzenna plecaka 0/1

• Złożoność czasowa: O(n · M) — dwie zagnieżdżone pętle przesuwają n elementów przez M+1 stanów pojemności.
• Złożoność kosmiczna: O(n · M) dla całej tablicy, sprowadzalne do O(M) przez keeping tylko poprzedni wiersz, kiedy trace-back nie jest potrzebny.

Czas wykonania to pseudowielomian: wielomianowy w wartości M, ale wykładniczy w bitach użytych do zakodowania M. Dlatego 0/1 Knapsack pozostaje NP-trudny, mimo że programowanie dynamiczne jest w praktyce wydajne.

Zastosowania problemu plecakowego 0/1

• Załadunek towarów, pakowanie kontenerów i kompletowanie zamówień w magazynach w ramach limitów wagowych.
• Podział budżetu pomiędzy projekty inwestycyjne o stałych kosztach i oczekiwanym zwrocie.
• Problemy z materiałem wyjściowym w procesie produkcyjnym, uniemożliwiające rozdzielenie poszczególnych sztuk.
• Schematy kryptograficzne, takie jak Merkle-Hellman, bazują na twardości plecakowej.
• Harmonogramowanie przy ograniczonych zasobach w przetwarzaniu w chmurze i rozmieszczanie zadań procesora.
• Selekcja funkcji w uczeniu maszynowym przy ustalonym budżecie funkcji.

FAQ