0/1 Rozwiązanie problemu z plecakiem przy użyciu przykładu programowania dynamicznego
Na czym polega problem z plecakiem?
Problem z plecakiem Algorytm jest bardzo pomocnym problemem w kombinatoryce. W supermarkecie znajduje się n paczek (n ≤ 100), paczka i ma wagę W[i] ≤ 100 i wartość V[i] ≤ 100. Do supermarketu włamuje się złodziej, nie może unieść ciężaru przekraczającego M (M ≤ 100 ). Problem do rozwiązania brzmi: jakie paczki zabierze złodziej, aby uzyskać najwyższą wartość?
Wejście:
- Maksymalna waga M i liczba paczek n.
- Tablica wag W[i] i odpowiadająca im wartość V[i].
Wyjście:
- Maksymalizuj wartość i odpowiednią wagę w udźwigu.
- Które paczki zabierze złodziej.
Algorytm plecakowy można dalej podzielić na dwa typy:
- Problem plecaka 0/1 z wykorzystaniem programowania dynamicznego. W tym typie algorytmu plecakowego każda paczka może zostać zabrana lub nie. Poza tym złodziej nie może zabrać ułamkowej części zabranej paczki ani zabrać paczki więcej niż raz. Ten typ można rozwiązać za pomocą podejścia programowania dynamicznego.
- Algorytm ułamkowego problemu plecakowego. Ten typ można rozwiązać za pomocą Greedy Strategy.
Jak rozwiązać problem plecakowy za pomocą programowania dynamicznego na przykładzie
W strategii dziel i rządź dzielisz problem do rozwiązania na podproblemy. Podproblemy są dalej podzielone na mniejsze podproblemy. To zadanie będzie kontynuowane, dopóki nie pojawią się podproblemy, które można łatwo rozwiązać. Jednak w procesie takiego podziału można wielokrotnie spotkać się z tym samym problemem.
Podstawową ideą programowania dynamicznego Knapsack jest użycie tabeli do przechowywania rozwiązań rozwiązanych podproblemów. Jeśli ponownie napotkasz podproblem, wystarczy, że weźmiesz rozwiązanie z tabeli, bez konieczności ponownego rozwiązywania go. Dlatego algorytmy zaprojektowane przez programowanie dynamiczne są bardzo skuteczne.
Aby rozwiązać problem za pomocą programowania dynamicznego, należy wykonać następujące zadania:
- Znajdź rozwiązania najmniejszych podproblemów.
- Poznaj wzór (lub regułę) pozwalający zbudować rozwiązanie podproblemu poprzez rozwiązania nawet najmniejszych podproblemów.
- Utwórz tabelę przechowującą rozwiązania podproblemów. Następnie oblicz rozwiązanie podproblemu według znalezionego wzoru i zapisz w tabeli.
- Z rozwiązanych podproblemów znajdziesz rozwiązanie pierwotnego problemu.
Przeanalizuj problem plecakowy 0/1
Analizując problem plecaka 0/1 za pomocą programowania dynamicznego, można znaleźć pewne zauważalne punkty. Wartość algorytmu plecakowego zależy od dwóch czynników:
- Ile pakietów jest rozważanych
- Pozostała waga, którą plecak może pomieścić.
Dlatego masz dwie zmienne ilości.
Dzięki programowaniu dynamicznemu masz przydatne informacje:
- funkcja celu będzie zależała od dwóch zmiennych wielkości
- tabela opcji będzie tabelą dwuwymiarową.
Jeżeli wywołanie B[i][j] to maksymalna możliwa wartość poprzez wybranie w pakietach {1, 2, …, i} z limitem wagi j.
- Maksymalna wartość przy wyborze w n pakietach z limitem wagowym M wynosi B[n][M]. Innymi słowy: gdy do wyboru jest i pakietów, B[i][j] jest wagą optymalną, gdy maksymalna waga plecaka wynosi j.
- Optymalna waga jest zawsze mniejsza lub równa maksymalnej masie: B[i][j] ≤ j.
Przykładowo: B[4][10] = 8. Oznacza to, że w optymalnym przypadku łączna waga wybranych paczek wynosi 8, gdy do wyboru są 4 pierwsze paczki (od 1 do 4 paczki) i maksymalna waga plecaka wynosi 10. Nie jest konieczne wybranie wszystkich 4 pozycji.
Wzór do obliczenia B[i][j]
Wprowadź, definiujesz:
- W[i], V[i] to z kolei waga i wartość paczki i, w której i
{1,…, n}.
- M to maksymalna waga, jaką może udźwignąć plecak.
W przypadku posiadania po prostu tylko 1 pakietu do wyboru. Obliczasz B[1][j] dla każdego j: co oznacza maksymalną wagę plecaka ≥ wagę 1. paczki
B[1][j] = W[1]
Przy limicie wagi j optymalny wybór pakietów {1, 2, …, i – 1, i} w celu uzyskania największej wartości będzie miał dwie możliwości:
- Jeśli pakiet i nie zostanie wybrany, B[i][j] jest maksymalną możliwą wartością poprzez wybranie spośród pakietów {1, 2, …, i – 1} z limitem wagi j. Ty masz:
B[i][j] = B[i – 1][j]
- Jeśli wybrany zostanie pakiet i (oczywiście rozważ ten przypadek tylko wtedy, gdy W[i] ≤ j), wówczas B[i][j] jest równe wartości V[i] pakietu i plus maksymalną wartość można uzyskać wybierając spośród paczki {1, 2, …, i – 1} z limitem wagowym (j – W[i]). To znaczy, jeśli chodzi o wartość, którą posiadasz:
B[i][j] = V[i] + B[i – 1][j – W[i]]
Ze względu na utworzenie B[i][j], które jest maksymalną możliwą wartością, B[i][j] będzie maksimum z powyższych 2 wartości.
Podstawy programowania dynamicznego
Musisz więc rozważyć, czy lepiej wybrać pakiet I, czy nie. Stamtąd masz formułę rekurencyjną w następujący sposób:
B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]
Łatwo jest zobaczyć B[0][j] = maksymalna możliwa wartość poprzez wybranie pakietu z 0 = 0.
Oblicz tabelę opcji
Budujesz tabelę opcji w oparciu o powyższą formułę rekurencyjną. Aby sprawdzić, czy wyniki są poprawne (jeśli nie dokładnie, przebudowujesz funkcję celu B[i][j]). Tworząc funkcję celu B[i][j] i tabelę opcji, zorientujesz śledzenie.
Tabela opcji B zawiera n + 1 wierszy, M + 1 kolumn,
- Po pierwsze, wypełniona podstawa programowania dynamicznego: Linia 0 zawiera wszystkie zera.
- Używając formuł rekurencyjnych, użyj linii 0 do obliczenia linii 1, użyj linii 1 do obliczenia linii 2 itd. … aż do obliczenia wszystkich linii.
Wyśledzić
Przy obliczaniu tabeli opcji interesuje Cię B[n][M], czyli maksymalna wartość uzyskana przy wyborze we wszystkich n pakietach z limitem wagowym M.
- If B[n][M] = B[n – 1][M] wówczas pakiet n nie jest wybrany, śledzisz B[n – 1][M].
- If B[n][M] ≠ B[n – 1][M], zauważasz, że optymalny wybór ma pakiet n i ślad B[n – 1][M – W[n]].
Kontynuuj śledzenie, aż dojdziesz do wiersza 0 tabeli opcji.
Algorytm przeglądania tabeli opcji w celu znalezienia wybranych pakietów
Uwaga: Jeśli B[i][j] = B[i – 1][j], pakiet i nie jest wybrany. B[n][W] to optymalna sumaryczna wartość paczki umieszczonej w plecaku.
Kroki śledzenia:
- Krok 1: Zaczynając od i = n, j = M.
- Krok 2: Spójrz w kolumnę j, od dołu do góry, znajdź linię i taką, że B[i][j] > B[i – 1][j]. Zaznacz wybrany pakiet i: Wybierz [i] = true;
- Krok 3: j = B[i][j] – W[i]. Jeśli j > 0, przejdź do kroku 2, w przeciwnym wypadku przejdź do kroku 4
- Krok 4: Na podstawie tabeli opcji wydruku wybranych pakietów.
Java Code
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: "); while (n != 0) { if (B[n][M] != B[n - 1][M]) { System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]); M = M - W[n-1]; } n--; } }
Wyjaśnienie kodu plecaka:
- Utwórz tabelę B[][]. Ustaw domyślną wartość dla każdej komórki na 0.
- Zbuduj tabelę B[][] w sposób oddolny. Oblicz tabelę opcji za pomocą wzoru wyszukiwania.
- Oblicz B[i][j]. Jeśli nie wybierzesz pakietu I.
- Następnie oceń: jeśli wybierzesz pakiet i, będzie to bardziej korzystne niż zresetowanie B[i][j].
- Prześledź tabelę od wiersza n do wiersza 0.
- Jeśli wybierzesz pakiet nr. Po wybraniu pakietu n, można dodać tylko wagę M – W[n – 1].
W tym samouczku masz dwa przykłady. Oto kod Java do uruchomienia powyższego programu z dwoma przykładami:
public void run() { /* * Pack and Weight - Value */ //int W[] = new int[]{3, 4, 5, 9, 4}; int W[] = new int[]{12, 2, 1, 1, 4}; //int V[] = new int[]{3, 4, 4, 10, 4}; int V[] = new int[]{4, 2, 1, 2, 10}; /* * Max Weight */ //int M = 11; int M = 15; int n = V.length; /* * Run the algorithm */ knapsackDyProg(W, V, M, n); }
Masz dane wyjściowe:
- Pierwszy przykład:
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
- Drugi przykład:
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