Zoeken…


Opmerkingen

Het knapzak- of rugzakprobleem is een probleem bij combinatorische optimalisatie . Gegeven een set items, elk met een gewicht en een waarde, bepaalt u het aantal van elk item dat u in een verzameling wilt opnemen, zodat het totale gewicht kleiner is dan of gelijk is aan een bepaalde limiet en de totale waarde zo groot mogelijk is. Het ontleent zijn naam aan het probleem van iemand die wordt beperkt door een knapzak met een vaste maat en het moet vullen met de meest waardevolle items.

Het probleem doet zich vaak voor bij de toewijzing van middelen waar financiële beperkingen zijn en wordt bestudeerd op gebieden zoals combinatoriek , informatica , complexiteitstheorie , cryptografie , toegepaste wiskunde en dagelijkse fantasiesporten .

Het knapzakprobleem is al meer dan een eeuw bestudeerd, met vroege werken die teruggaan tot 1897. De naam "knapzakprobleem" dateert uit de vroege werken van de wiskundige Tobias Dantzig (1884-1956) en verwijst naar het alledaagse probleem van je meest waardevolle of nuttige spullen inpakken zonder je bagage te overladen.

0-1 Knapzakprobleem

Stel dat u wordt gevraagd, gezien het totale gewicht dat u kunt dragen op uw knapzak en sommige artikelen met hun gewicht en waarden, hoe kunt u die artikelen zodanig nemen dat de som van hun waarden maximaal is, maar de som van hun gewichten het totale gewicht dat u kunt dragen niet overschrijden? De 0-1 geeft aan of u het item kiest of niet. Ook hebben we een hoeveelheid van elk item. Dit betekent dat u het item niet kunt splitsen. Als het geen 0-1 knapzakprobleem was , betekent dit dat als je de items had kunnen splitsen, er een hebzuchtige oplossing voor was, die fractionele knapzakprobleem wordt genoemd.

Laten we ons nu concentreren op ons huidige probleem. Laten we bijvoorbeeld zeggen dat we een knapzakcapaciteit van 7 hebben . We hebben 4 items. Hun gewichten en waarden zijn:

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

Een brute force-methode is het nemen van alle mogelijke combinaties van items. Dan kunnen we hun totale gewichten berekenen en uitsluiten die de capaciteit van onze knapzak te boven gaan en degene vinden die ons maximale waarde geeft. Voor 4 items moeten we controleren ( 4! - 1 ) = 23 mogelijke combinaties (met uitzondering van één zonder items). Dit is vrij omslachtig wanneer het aantal items toeneemt. Hier zijn een paar aspecten die we kunnen opmerken, namelijk:

  • We kunnen kleinere items nemen en de maximale waarde berekenen die we kunnen krijgen met behulp van die items en ze combineren. Ons probleem kan dus worden onderverdeeld in subproblemen.
  • Als we de combinaties berekenen voor item {1,2} , kunnen we dit gebruiken wanneer we {1, 2, 3} berekenen.
  • Als we het gewicht minimaliseren en de waarde maximaliseren, kunnen we onze optimale oplossing vinden.

Om deze redenen zullen we dynamische programmering gebruiken om ons probleem op te lossen. Onze strategie zal zijn: wanneer een nieuw item komt, zullen we controleren of we het item kunnen kiezen of niet en opnieuw zullen we de items kiezen die ons maximale waarde geven. Als we nu het artikel kiezen, is onze waarde de waarde van het artikel, plus de waarde die we kunnen krijgen door de waarde af te trekken van onze capaciteit en het maximum dat we kunnen krijgen voor dat resterende gewicht. Als we het item niet kiezen, kiezen we de items die ons maximale waarde geven zonder het item op te nemen. Laten we proberen het te begrijpen met ons voorbeeld:

We nemen een 2D-array- tabel , waarbij het aantal kolommen de maximale waarde is die we kunnen krijgen door de items + 1 te nemen. En het aantal rijen zal hetzelfde zijn als het aantal items. Onze reeks ziet eruit als:

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

We hebben voor elk gemak het gewicht en de waarde van elk item in de array opgenomen. Onthoud dat deze geen deel uitmaken van de array, deze zijn alleen voor berekeningsdoeleinden, u hoeft deze waarden niet in een tabelarray op te slaan.

Onze eerste kolom is gevuld met 0 . Het betekent dat als onze maximale capaciteit 0 is , ongeacht welk item we hebben, omdat we geen items kunnen selecteren, onze maximale waarde 0 zal zijn. Laten we beginnen met tabel [0] [1] . Wanneer we tabel [1] [1] invullen, vragen we ons af of onze maximale capaciteit 1 was en we alleen het eerste item hadden, wat zou onze maximale waarde zijn? Het beste wat we kunnen doen is 1 , door het item te kiezen. Voor tabel [0] [2] betekent dit dat als onze maximale capaciteit 2 is en we alleen het eerste item hebben, de maximale waarde die we kunnen krijgen 1 is . Dit is hetzelfde voor tabel [0] [3] , tabel [0] [4] , tabel [0] [5] , tabel [0] [6] en tabel [0] [7] . Dit komt omdat we slechts één item hebben, wat ons waarde 1 geeft . Omdat we slechts 1 hoeveelheid van elk artikel hebben, maakt het niet uit hoe we de capaciteit van onze knapzak vergroten, van 1 artikel is 1 de beste waarde die we kunnen maken. Onze reeks ziet er dus uit als:

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

Verder gaan we voor tabel [1] [1] ons af of we item 1 en 2 hadden en of de maximale capaciteit van onze knapzak 1 was , wat is de maximale waarde die we kunnen krijgen? Als we zowel item 1 als 2 nemen , is het totale gewicht 4 , wat onze huidige knapzakcapaciteit overschrijdt. Dus item 2 kan niet worden geselecteerd. Wat is nu het beste wat we kunnen doen zonder item 2 te nemen ? De waarde van boven, dat wil zeggen tabel [0] [1], die de maximale waarde bevat die we kunnen krijgen als we maximale capaciteit 1 hadden en het tweede item niet hadden gekozen. Voor tabel [1] [2] , aangezien 2 minder is dan gewicht [2] , dat is het gewicht van het tweede item, kunnen we het item niet nemen. We kunnen dus vaststellen dat, als het gewicht van het huidige item groter is dan onze maximale capaciteit, we dat item niet kunnen meenemen. In dit geval nemen we gewoon de waarde van boven, die de maximale waarde vertegenwoordigt die we kunnen nemen, exclusief het item.

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

Nu voor tabel [1] [3] hebben we twee keuzes, aangezien onze maximale capaciteit gelijk is aan ons huidige gewicht.

  • We kiezen het item en voegen de waarde toe met de maximale waarde die we kunnen krijgen van andere resterende items nadat we dit item hebben ingenomen.
  • We kunnen dit item uitsluiten.

Onder de twee keuzes kiezen we degene waaruit we maximale waarde kunnen halen. Als we het item selecteren, krijgen we: waarde voor dit item + maximale waarde van de rest van de items na het nemen van dit item = 4 + 0 = 4 . We krijgen 4 (waarde van het item) uit onze gewichtsreeks en de 0 (maximale waarde die we kunnen krijgen van de rest van de items na het nemen van dit item) komt door 1 stap hoger en 3 stappen terug te gaan. Dat is tabel [0] [0] . Waarom? Als we het artikel nemen, is onze resterende capaciteit 3 - 3 = 0 en is het resterende artikel het eerste artikel. Als u zich herinnert, slaat tabel [0] [0] de maximale waarde op die we kunnen krijgen als onze capaciteit 0 was en we alleen het eerste item hadden. Als we het item niet selecteren, komt de maximale waarde die we kunnen krijgen uit 1 stap hierboven, dat is 1 . We nemen nu het maximum van deze twee waarden ( 4 , 1 ) en stellen Tabel [1] [2] = 4 in . Voor tabel [1] [4] , aangezien 4 , de maximale knapzakcapaciteit groter is dan 3 , het gewicht van ons huidige item, hebben we opnieuw twee opties. We nemen max ( gewicht [2] + tabel [0] [4-gewicht [2]] , tabel [0] [4] ) = max ( gewicht [2] + tabel [0] [1] , tabel [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

Met behulp van deze twee formules kunnen we de hele tabelarray vullen. Onze reeks ziet eruit als:

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

Hier, de laatste waarde die we in onze array hebben ingevoegd, tabel [3] [7], bevat onze vereiste maximale waarde. Dit is de maximale waarde die we kunnen krijgen als we 4 items hadden en onze maximale capaciteit van de knapzak 7 was .

Hier is één ding dat we moeten onthouden dat, zelfs voor de eerste rij, het gewicht groter kan zijn dan de capaciteit van de knapzak. We moeten nog een beperking behouden om de waarde te controleren terwijl we de eerste rij vullen. Of we kunnen gewoon een andere rij nemen en alle waarden van de eerste rij op 0 zetten . De pseudo-code ziet er als volgt uit:

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]

De tijdcomplexiteit van dit algoritme is O(n*maxCapacity) , waarbij n het aantal items is en maxCapacity de maximale capaciteit van onze knapzak is.

Tot nu toe hebben we de maximale waarde gevonden die we uit ons voorbeeld kunnen halen. Er blijft nog een vraag over. Wat zijn de werkelijke items? We zullen de waarden terugvinden in onze tabel array om uit te vinden de items die we hebben genomen. We volgen twee strategieën:

  • Voor elk item, als de waarde uit de bovenstaande positie komt, hebben we het huidige item niet genomen. We gaan 1 stap hoger.
  • Als de waarde niet uit de bovenstaande positie komt, hebben we het item genomen. Dus gaan we 1 stap boven en x gaat terug waar x het gewicht van het huidige item is.

De pseudo-code zal zijn:

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

Als we ons voorbeeld herhalen, krijgen we:

Retraced Array

Hieruit kunnen we zeggen dat we item 2 en 3 kunnen nemen om de maximale waarde te krijgen.



Modified text is an extract of the original Stack Overflow Documentation
Licentie onder CC BY-SA 3.0
Niet aangesloten bij Stack Overflow