Het knapzakprobleem
Een wandelaar met een gewichtsgrens, een dief met een zak, een bedrijf met een budget en een lijst projecten: ze staan allemaal voor dezelfde vraag. Wat moet erin om de meeste waarde te krijgen zonder over de grens te gaan? Dat is het knapzakprobleem, en dynamisch programmeren lost het exact op als de gewichten hele getallen van gemiddelde grootte zijn.
Het probleem
Er zijn n voorwerpen, elk met een gewicht en een waarde, en een rugzak die hoogstens een gewicht W kan dragen. Kies een verzameling voorwerpen met een totaalgewicht van hoogstens W en een zo groot mogelijke totale waarde. Elk voorwerp gaat er in zijn geheel in of blijft eruit; daarom heet het het 0/1-knapzakprobleem. Met n voorwerpen zijn er 2ⁿ mogelijke verzamelingen, dus ze allemaal proberen wordt al snel onmogelijk.
De tabel
Laat best[i][w] de hoogste waarde zijn die in gewicht w past met alleen de eerste i voorwerpen. Dan is best[0][w] = 0, en voor elke volgende rij zijn er twee keuzes: voorwerp i weglaten, wat best[i − 1][w] geeft, of, als het gewicht wᵢ past, het inpakken, wat de waarde ervan plus best[i − 1][w − wᵢ] geeft. De grootste van de twee is best[i][w]. Als je de tabel rij voor rij vult, zijn beide cellen die nodig zijn altijd al klaar.
Een voorbeeld
Neem een capaciteit van 7 en vier voorwerpen met gewichten 1, 3, 4 en 5 en waarden 1, 4, 5 en 7. Met alleen het eerste voorwerp is elke capaciteit vanaf 1 precies 1 waard. Met het tweede erbij kan capaciteit 4 beide bevatten, voor 5. Met het derde erbij kan capaciteit 7 voorwerpen 2 en 3 bevatten, voor 9. Het vierde voorwerp, gewicht 5 en waarde 7, kan bij capaciteit 6 of 7 samen met voorwerp 1 op 8 komen, maar 9 is beter, dus de cel rechtsonder is 9: pak de voorwerpen met gewicht 3 en 4 in.
Hoe moeilijk is het?
De tabel heeft ongeveer n·W stappen nodig. Dat lijkt snel, maar W is een getal, en een getal met d cijfers kan zo groot zijn als 10 tot de macht d, dus het werk groeit exponentieel met de lengte van de invoer. Het knapzakprobleem is NP-moeilijk; het was een van de 21 NP-volledige problemen van Richard Karp uit 1972. In de praktijk kunnen de tabel, branch and bound en goede benaderingsschema's grote echte gevallen goed aan.
Geschiedenis en toepassingen
De naam gaat terug op de wiskundige Tobias Dantzig in het begin van de 20e eeuw, en zijn zoon George Dantzig gaf er in 1957 een klassieke gulzige methode voor. Knapzakproblemen duiken op bij budgettering en portefeuillekeuze, bij het snijden van grondstoffen met zo weinig mogelijk afval, bij het laden van vracht en zelfs in de vroege cryptografie met publieke sleutels: het Merkle–Hellman-cryptosysteem uit 1978 was op een knapzakprobleem gebouwd en werd een paar jaar later gekraakt.
Probeer het zelf
Open de app, ga naar de weergave Tabel en druk op Stap. De oranje cel wordt gevuld, en de blauwe cellen zijn de twee die ze vergelijkt: de cel direct erboven en, in de rij erboven, de cel die het gewicht van het voorwerp naar links ligt. Na de laatste cel klimt het teruglezen in oranje omhoog vanuit de hoek rechtsonder, en verschijnen de ingepakte voorwerpen onder de tabel.
Veelgestelde vragen
Wat is het verschil tussen het 0/1-, het begrensde en het onbegrensde knapzakprobleem?
In de 0/1-versie wordt elk voorwerp hoogstens één keer genomen. In de begrensde versie heeft elk voorwerp een beperkt aantal exemplaren, en in de onbegrensde versie een willekeurig aantal. De tabel verandert daartussen maar weinig.
Is de gulzige methode ooit juist bij het knapzakprobleem?
Bij het fractionele knapzakprobleem, waarin je voorwerpen kunt splitsen, is eerst de beste waarde per gewicht nemen optimaal. Bij hele voorwerpen kan het er ver naast zitten, hoewel de beste van de gulzige oplossing en het waardevolste losse voorwerp altijd minstens de helft van de beste waarde oplevert.
Hoeveel geheugen heeft de tabel nodig?
(n + 1)·(W + 1) cellen voor de volledige tabel, en die heb je nodig om de voorwerpen terug te lezen. Als je alleen de beste waarde wilt, is één rij van W + 1 cellen genoeg, gevuld van rechts naar links.
Is het knapzakprobleem hetzelfde als subset sum?
Subset sum (het deelsomprobleem) is het speciale geval waarin de waarde van elk voorwerp gelijk is aan het gewicht en de vraag is of de rugzak precies vol kan. Het is ook NP-volledig en wordt met hetzelfde soort tabel opgelost.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer het knapzakprobleem