dynamic-programming
Problem z plecakiem

Uwagi

0-1 Problem z plecakiem

Załóżmy, że zapytano cię, biorąc pod uwagę całkowitą masę, jaką możesz nosić na plecaku i niektóre przedmioty wraz z ich wagą i wartościami, jak możesz wziąć te przedmioty w taki sposób, aby suma ich wartości była maksymalna, ale suma ich ciężarów nie przekracza całkowitej masy, którą możesz unieść? 0-1 oznacza, że albo wybierzesz przedmiot, albo nie. Również mamy jedną ilość każdego elementu. Oznacza to, że nie możesz podzielić przedmiotu. Jeśli nie był to problem plecakowy 0-1 , oznacza to, że gdybyś mógł podzielić przedmioty, istnieje chciwe rozwiązanie, które nazywa się problemem ułamkowego plecaka .

Na razie skoncentrujmy się na naszym problemie. Załóżmy na przykład, że mamy pojemność plecaka 7 . Mamy 4 przedmioty. Ich wagi i wartości to:

+----------+---+---+---+---+
|   Item   | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
|  Weight  | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
|   Value  | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+

Jedną metodą brutalnej siły byłoby przyjmowanie wszystkich możliwych kombinacji przedmiotów. Następnie możemy obliczyć ich masy całkowite i wykluczyć te, które przekraczają pojemność naszego plecaka i znaleźć ten, który daje nam maksymalną wartość. Dla 4 przedmiotów będziemy musieli sprawdzić ( 4! - 1 ) = 23 możliwe kombinacje (z wyjątkiem jednej bez przedmiotów). Jest to dość kłopotliwe, gdy liczba przedmiotów wzrasta. Oto kilka aspektów, które możemy zauważyć:

• Możemy wziąć mniejsze przedmioty i obliczyć maksymalną wartość, jaką możemy uzyskać, używając tych przedmiotów i połączyć je. Nasz problem można podzielić na podproblemy.
• Jeśli obliczymy kombinacje dla elementu {1,2} , możemy go użyć, obliczając {1, 2, 3} .
• Jeśli zminimalizujemy wagę i zmaksymalizujemy wartość, możemy znaleźć nasze optymalne rozwiązanie.

Z tych powodów użyjemy programowania dynamicznego, aby rozwiązać nasz problem. Nasza strategia będzie następująca: za każdym razem, gdy pojawi się nowy przedmiot, sprawdzimy, czy możemy go wybrać, czy nie, i ponownie wybierzemy przedmioty, które dają nam maksymalną wartość. Teraz, jeśli wybierzemy przedmiot, naszą wartością będzie wartość przedmiotu plus wartość, którą możemy uzyskać, odejmując wartość od naszej pojemności i maksimum, jakie możemy uzyskać za pozostałą wagę. Jeśli nie wybieramy przedmiotu, wybieramy przedmioty, które dają nam maksymalną wartość bez uwzględnienia przedmiotu. Spróbujmy to zrozumieć na naszym przykładzie:

Weźmiemy tabelę tablicy 2D, gdzie liczba kolumn będzie wartością maksymalną możemy uzyskać poprzez elementy + 1. a liczba wierszy będzie taka sama jak liczba elementów. Nasza tablica będzie wyglądać następująco:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

Dla wygody włączyliśmy wagę i wartość każdego elementu do tablicy. Pamiętaj, że nie są one częścią tablicy, służą wyłącznie do celów obliczeniowych, nie musisz przechowywać tych wartości w tablicy tabel .

Nasza pierwsza kolumna jest wypełniona 0 . Oznacza to, że jeśli nasza maksymalna pojemność wynosi 0 , bez względu na to, jaki przedmiot mamy, ponieważ nie możemy wybrać żadnych przedmiotów, nasza maksymalna wartość wyniesie 0 . Zacznijmy od tabeli [0] [1] . Gdy wypełniamy tabelę [1] [1] , zadajemy sobie pytanie, czy nasza maksymalna pojemność wynosiła 1 i czy mieliśmy tylko pierwszy przedmiot, jaka byłaby nasza maksymalna wartość? Najlepsze, co możemy zrobić, to 1 , wybierając przedmiot. W przypadku tabeli [0] [2] oznacza to, że jeśli nasza maksymalna pojemność wynosi 2 i mamy tylko pierwszy element, maksymalna wartość, którą możemy uzyskać, to 1 . Będzie tak samo dla Tabeli [0] [3] , Tabeli [0] [4] , Tabeli [0] [5] , Tabeli [0] [6] i Tabeli [0] [7] . Jest tak, ponieważ mamy tylko jeden przedmiot, co daje nam wartość 1 . Ponieważ mamy tylko 1 ilość każdego przedmiotu, bez względu na to, jak zwiększymy pojemność naszego plecaka, z jednego przedmiotu 1 jest najlepszą wartością, jaką możemy zrobić. Nasza tablica będzie wyglądać następująco:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

Przechodząc dalej do tabeli [1] [1] , zadajemy sobie pytanie, czy mieliśmy pozycje 1 i 2, a jeśli maksymalna pojemność naszego plecaka wynosiła 1 , jaka jest maksymalna wartość, którą możemy uzyskać? Jeśli weźmiemy zarówno przedmiot 1, jak i 2 , całkowita waga wyniesie 4 , co przekroczy naszą obecną pojemność plecaka. Dlatego nie można wybrać pozycji 2 . Co teraz możemy zrobić bez zabrania punktu 2 ? Wartość z góry, czyli Tabela [0] [1], która zawiera maksymalną wartość, jaką możemy uzyskać, gdybyśmy mieli maksymalną pojemność 1 i nie wybraliśmy drugiego elementu. W przypadku tabeli [1] [2] , ponieważ 2 jest mniejsze niż waga [2] , czyli waga drugiego przedmiotu, nie możemy wziąć przedmiotu. Możemy więc ustalić, że jeśli waga bieżącego przedmiotu jest większa niż nasza maksymalna pojemność, nie możemy wziąć tego przedmiotu. W takim przypadku po prostu weźmiemy wartość od góry, która reprezentuje maksymalną wartość, którą możemy przyjąć bez elementu.

if weight[i] > j
    Table[i][j] := Table[i-1][j]
end if

Teraz dla tabeli [1] [3], ponieważ nasza maksymalna pojemność jest równa naszej obecnej wadze, mamy dwie możliwości.

• Wybieramy przedmiot i dodajemy jego wartość do maksymalnej wartości, jaką możemy uzyskać z pozostałych pozostałych przedmiotów po zabraniu tego przedmiotu.
• Możemy wykluczyć ten przedmiot.

Spośród dwóch opcji wybieramy tę, z której możemy uzyskać maksymalną wartość. Jeśli wybierzemy przedmiot, otrzymamy: wartość tego przedmiotu + maksymalna wartość z pozostałych przedmiotów po przyjęciu tego przedmiotu = 4 + 0 = 4 . Otrzymujemy 4 (wartość przedmiotu) z naszej tablicy wag, a 0 (maksymalna wartość, którą możemy uzyskać z reszty przedmiotów po zabraniu tego przedmiotu) pochodzi, przechodząc o 1 krok wyżej i 3 kroki wstecz. To jest tabela [0] [0] . Dlaczego? Jeśli weźmiemy przedmiot, nasza pozostała pojemność wyniesie 3 - 3 = 0, a pozostały przedmiot będzie pierwszym przedmiotem. Cóż, jeśli przypomnisz sobie, Tabela [0] [0] przechowuje maksymalną wartość, jaką możemy uzyskać, jeśli nasza pojemność wynosi 0 i mamy tylko pierwszy przedmiot. Teraz, jeśli nie wybieramy przedmiotu, maksymalna wartość, którą możemy uzyskać, pochodzi z 1 kroku powyżej, czyli 1 . Teraz bierzemy maksimum z tych dwóch wartości ( 4 , 1 ) i ustawiamy Tabela [1] [2] = 4 . W tabeli [1] [4] , od 4 , maksymalna pojemność plecaka jest większa niż 3 , waga naszego obecnego produktu, znów mamy dwie opcje. Przyjmujemy maks. ( Waga [2] + tabela [0] [4-waga [2]] , tabela [0] [4] ) = max ( waga [2] + tabela [0] [1] , tabela [0]) [4] ) = maks. ( 4 + 1 , 1 ) = 5 .

if weight[i] <= j
    w := weight[i]
    Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
end if

Za pomocą tych dwóch formuł możemy wypełnić całą tablicę tabel . Nasza tablica będzie wyglądać następująco:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+

Tutaj ostatnia wartość, którą wstawiliśmy do naszej tablicy, Tabela [3] [7] zawiera naszą wymaganą maksymalną wartość. Jest to maksymalna wartość, jaką możemy uzyskać, gdybyśmy mieli 4 przedmioty, a nasza maksymalna pojemność plecaka wynosiła 7 .

Tutaj musimy pamiętać, że nawet w pierwszym rzędzie waga może być większa niż pojemność plecaka. Będziemy musieli zachować kolejne ograniczenie, aby sprawdzić wartość podczas wypełniania pierwszego wiersza. Lub możemy po prostu wziąć kolejny wiersz i ustawić wszystkie wartości pierwszego rzędu na 0 . Pseudo-kod wyglądałby następująco:

Procedure Knapsack(Weight, Value, maxCapacity):
n := Item.size - 1
Table[n+1][maxCapacity+1]
for i from 0 to n
    Table[i][0] := 0
end for
for j from 1 to maxCapacity
    if j >= Weight[0]
        Table[0][j] := Weight[0]
    else
        Table[0][j] := 0
    end if
end for
for i from 1 to n
    for j from 1 to maxCapacity
        if Weight[i] >= j                                            //can't pick the item
            Table[i][j] := Table[i-1][j]        
        else                                                        //can pick the item
            w := Weight[i]
            Table[i][j] := max(w + Table[i-1][j-w], Table[i-1][j])
        end if
    end for
end for
Return Table[n][maxCapacity]

Złożoność czasowa tego algorytmu wynosi O(n*maxCapacity) , gdzie n to liczba przedmiotów, a maxCapacity to maksymalna pojemność naszego plecaka.

Jak dotąd znaleźliśmy maksymalną wartość, jaką możemy uzyskać z naszego przykładu. Pozostaje jedno pytanie. Jakie są rzeczywiste przedmioty? Prześledzimy wartości w naszej tablicy tabel, aby znaleźć przedmioty, które wzięliśmy. Będziemy przestrzegać dwóch strategii:

• W przypadku dowolnego przedmiotu, jeśli wartość pochodzi z powyższej pozycji, nie wzięliśmy bieżącego przedmiotu. Idziemy o krok wyżej.
• Jeśli wartość nie pochodzi z powyższej pozycji, wzięliśmy przedmiot. Idziemy o 1 krok wyżej i x cofamy się, gdzie x jest wagą bieżącego przedmiotu.

Pseudo-kod będzie:

Procedure printItems(Table, maxCapacity, Value):
i := Item.size - 1
j := maxCapacity
while j is not equal to 0
    if Table[i][j] is equal to Table[i-1][j]
        i := i - 1
    else
        Print: i
        j := j - weight[i]
        i := i - 1
    end if
end while

Jeśli prześledzimy nasz przykład, otrzymamy:

Z tego możemy powiedzieć, że możemy wziąć punkty 2 i 3, aby uzyskać maksymalną wartość.