dynamic-programming
Ryggsäckproblem

Anmärkningar

0-1 Ryggsäckproblem

Anta att du blir frågad, med tanke på den totala vikten du kan bära din ryggsäck och vissa föremål med deras vikt och värden, hur kan du ta dessa föremål på ett sådant sätt att summan av deras värden är högst, men summan av deras vikter don inte överskrider den totala vikten du kan bära? 0-1 anger antingen att du väljer artikeln eller inte. Vi har också en mängd av varje artikel. Det betyder att du inte kan dela föremålet. Om det inte var ett 0-1 ryggsäckproblem , betyder det att om du kunde dela upp artiklarna, finns det en girig lösning på det, som kallas bråknappsäckproblem .

Låt oss nu koncentrera oss på vårt problem. Låt oss till exempel säga att vi har en ryggsäckskapacitet på 7 . Vi har 4 artiklar. Deras vikter och värden är:

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

En metod för brute force skulle vara att ta alla möjliga kombinationer av objekt. Då kan vi beräkna deras totala vikter och utesluta dem som överskrider vår ryggsäcks kapacitet och ta reda på den som ger oss högsta värde. För fyra artiklar måste vi kontrollera ( 4! - 1 ) = 23 möjliga kombinationer (exklusive ett utan objekt). Detta är ganska besvärligt när antalet artiklar ökar. Här några aspekter vi kan märka, det vill säga:

• Vi kan ta mindre artiklar och beräkna det maximala värdet vi kan få med dessa objekt och kombinera dem. Så vårt problem kan delas upp i delproblem.
• Om vi beräknar kombinationerna för artikel {1,2} , kan vi använda den när vi beräknar {1, 2, 3} .
• Om vi minimerar vikten och maximerar värdet kan vi ta reda på vår optimala lösning.

Av dessa skäl använder vi dynamisk programmering för att lösa våra problem. Vår strategi kommer att vara: när en ny artikel kommer kommer vi att kontrollera om vi kan välja objektet eller inte och igen väljer vi de objekt som ger oss maximalt värde. Om vi nu väljer objektet kommer vårt värde att vara värdet på objektet, plus det värde vi kan få genom att subtrahera värdet från vår kapacitet och det maximala vi kan få för den återstående vikten. Om vi inte väljer föremålet, väljer vi de objekt som ger oss maximalt värde utan att inkludera föremålet. Låt oss försöka förstå det med vårt exempel:

Vi tar en tabell med 2D-arrayer, där antalet kolumner är det maximala värdet vi kan få genom att ta objekten + 1. Och antalet rader kommer att vara samma som antalet objekt. Vår matris kommer att se ut:

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

Vi har integrerat vikten och värdet på varje objekt i matrisen för vår bekvämlighet. Kom ihåg att detta är inte en del av matrisen, dessa är för beräkning syfte endast behöver du inte lagra dessa värden i tabellen array.

Vår första kolumn är fylld med 0 . Det betyder att om vår maximala kapacitet är 0 , oavsett vilken vara vi har, eftersom vi inte kan välja några objekt, kommer vårt högsta värde att vara 0 . Låt oss börja från tabell [0] [1] . När vi fyller tabell [1] [1] , frågar vi oss om vår maximala kapacitet var 1 och vi bara hade den första artikeln, vad skulle vara vårt högsta värde? Det bästa vi kan göra är 1 genom att plocka artikeln. För tabell [0] [2] betyder det att om vår maximala kapacitet är 2 och vi bara har den första artikeln, är det högsta värdet vi kan få 1 . Detta kommer att vara samma för tabell [0] [3] , tabell [0] [4] , tabell [0] [5] , tabell [0] [6] och tabell [0] [7] . Det beror på att vi bara har en artikel, vilket ger oss värde 1 . Eftersom vi har bara en kvantitet av varje objekt, oavsett hur vi öka kapaciteten i vår ryggsäck, från ett objekt, en är det bästa värdet som vi kan göra. Så vår matris kommer att se ut:

+-------+--------+---+---+---+---+---+---+---+---+
| 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 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

När vi fortsätter, för tabell [1] [1] , frågar vi oss själva, om vi hade artikel 1 och 2 och om den maximala kapaciteten för vår ryggsäck var 1 , vad är det maximala värdet vi kan få? Om vi tar både artikel 1 och 2 , blir totalvikten 4 , vilket kommer att överstiga vår nuvarande ryggsäckkapacitet. Så artikel 2 kan inte väljas. Vad är det bästa vi kan göra utan att ta punkt 2 ? Värdet uppifrån, det vill säga tabell [0] [1] som innehåller det maximala värdet vi kan få om vi hade maximal kapacitet 1 och vi inte valde den andra artikeln. För tabell [1] [2] , eftersom 2 är mindre än vikten [2] , det är vikten på den andra artikeln, kan vi inte ta artikeln. Så vi kan fastställa att om vikten på den aktuella artikeln är större än vår maximala kapacitet, kan vi inte ta den artikeln. I det här fallet tar vi helt enkelt värdet uppifrån, vilket representerar det maximala värdet vi kan ta exklusive objektet.

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

Nu för tabell [1] [3] eftersom vår maximala kapacitet är lika med vår nuvarande vikt har vi två val.

• Vi väljer artikeln och lägger till dess värde med det maximala värdet vi kan få från andra återstående artiklar efter att vi tagit denna artikel.
• Vi kan utesluta denna artikel.

Bland de två valen väljer vi det vi kan få maximalt värde från. Om vi väljer objektet får vi: värde för den här artikeln + maximivärde från resten av artiklarna efter att ha tagit den här artikeln = 4 + 0 = 4 . Vi får 4 (värdet på objektet) från vår vikt array och 0 (maxvärdet vi kan få från resten av objekten efter att ha tagit denna post) kommer genom att gå en steg över och 3 steg tillbaka. Det är tabell [0] [0] . Varför? Om vi tar föremålet blir vår återstående kapacitet 3 - 3 = 0 och återstående artikel blir den första artikeln. Tja, om du kommer ihåg Tabell [0] [0] lagrar det maximala värdet vi kan få om vår kapacitet var 0 och vi bara hade den första artikeln. Om vi inte väljer objektet kommer det högsta värdet vi kan få från 1 steg ovan, det vill säga 1 . Nu tar vi maximalt av dessa två värden ( 4 , 1 ) och ställer in tabell [1] [2] = 4 . För tabell [1] [4] , sedan 4 är den maximala ryggsäckkapaciteten större än 3 , vikten på vår nuvarande artikel, vi har återigen två alternativ. Vi tar max ( vikt [2] + tabell [0] [4-vikt [2]] , tabell [0] [4] ) = max ( vikt [2] + tabell [0] [1] , tabell [0] [4] ) = max ( 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

Med hjälp av dessa två formler kan vi fylla i hela tabellen . Vår matris kommer att se ut:

+-------+--------+---+---+---+---+---+---+---+---+
| 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 |
+-------+--------+---+---+---+---+---+---+---+---+

Här innehåller det sista värdet som vi infogade i vårt array, tabell [3] [7] vårt nödvändiga maximivärde. Detta är det högsta värdet vi kan få om vi hade fyra artiklar och vår maximala kapacitet på ryggsäcken var 7 .

Här måste vi komma ihåg att även för den första raden kan vikten vara större än ryggsäckens kapacitet. Vi måste hålla en annan begränsning för att kontrollera värdet medan vi fyller den första raden. Eller så kan vi helt enkelt ta en ny rad och ställa in alla värden på den första raden till 0 . Pseudokoden ser ut som:

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]

Tidskomplexiteten för denna algoritm är O(n*maxCapacity) , där n är antalet artiklar och maxCapacity är den maximala kapaciteten för vår ryggsäck.

Hittills har vi hittat det maximala värdet vi kan få från vårt exempel. En fråga återstår fortfarande. Vilka är de faktiska artiklarna? Vi kommer att spåra värdena i vår tabell array för att ta reda på de punkter vi har tagit. Vi följer två strategier:

• För något objekt, om värdet kommer från positionen ovan, tog vi inte det aktuella objektet. Vi går ett steg ovan.
• Om värdet inte kommer från positionen ovan tog vi föremålet. Så vi går 1 steg ovan och x går tillbaka där x är vikten på det aktuella objektet.

Pseudokoden kommer att vara:

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

Om vi återgår till vårt exempel får vi:

Från detta kan vi säga det, vi kan ta punkt 2 och 3 för att få det maximala värdet.