Voorspel — waar of niet waar?
Leerdoel: je toetst je intuïtie over 0/1 knapsack voordat je begint te programmeren.
Lees elke stelling. Bedenk eerst je antwoord. Klap dan pas open.
Stelling 1
"Het item met de hoogste waarde zit altijd in de beste rugzak."
Antwoord
Niet waar.
Voorbeeld: rugzak 5 kg, item X = (waarde 10, gewicht 5), items Y en Z = elk (waarde 6, gewicht 2). X is het waardevolst, maar de beste rugzak is Y + Z: waarde 12 tegen 10.
Het waardevolste item kan zoveel ruimte pakken dat het de rest blokkeert. In het voorbeeld van de les zag je hetzelfde: item 5 is het meest waard en zit niet in de beste rugzak.
Stelling 2
"Rugzak 50 kg, items (waarde 60, gewicht 10), (100, 20) en (120, 30). Het item met de beste waarde per kilo zit in de beste rugzak."
Antwoord
Niet waar.
Waarde per kilo: 6, 5 en 4. Het eerste item is per kilo het beste, maar de beste rugzak is het tweede en het derde item samen: precies 50 kg en 220 waard. Met het eerste item erbij past hoogstens nog het tweede: 160.
Steeds het item met de beste waarde per kilo pakken heet greedy. Het gaat mis omdat het per item kijkt, terwijl het antwoord van de combinatie afhangt. Daarom vult dit hoofdstuk een tabel in die elke combinatie meeweegt. Bij de fractionele knapsack, waar je een halve item mag pakken, werkt greedy wél.
Stelling 3
"Bij N items zijn er 2ᴺ mogelijke combinaties."
Antwoord
Waar.
Elk item heeft twee keuzes (skip of meenemen). Bij N items: 2 × 2 × … × 2 (N keer) = 2ᴺ.
Bij N = 20 zijn dat ruim een miljoen, bij N = 30 al een miljard. Al die combinaties één voor één proberen is dan geen optie meer.
Stelling 4
"De tabel heeft altijd
(n+1) × (W+1)cellen."
Antwoord
Waar.
Eén extra rij (voor i = 0 = geen items, allemaal 0) en één extra
kolom (voor w = 0 = lege rugzak, allemaal 0). Die "0-rij" en
"0-kolom" zijn de basisgevallen waaruit we de tabel opbouwen.
Bij 5 items en W=11 (het voorbeeld van de les) is dat dus 6 × 12 = 72
cellen. Ongeacht wat de waardes of gewichten van de items zijn.
Stelling 5
"Als een item zwaarder is dan de capaciteit van een cel, krijgt die cel de waarde van de cel erboven: de beste rugzak zonder dit item."
Antwoord
Waar.
Meenemen kan niet: dan zou de capaciteit negatief worden. Wat overblijft is wat je zonder dit item kunt halen, en dat staat al in de cel erboven. Daarom kopieer je hem.
In code is dat de if gewicht > w: die je meteen naar de kopie brengt,
zonder de meenemen-tak te proberen.
Stelling 6
"Met de tabel kun je ook 100 items aan, zolang de capaciteit niet gigantisch wordt."
Antwoord
Waar.
Bij 100 items en een capaciteit van 1000 heeft de tabel 101 × 1001,
ruim 100.000 cellen. Elke cel is één vergelijking, dus dat is in een
fractie van een seconde klaar.
Vergelijk dat met alle combinaties afgaan: bij 30 items zijn dat er al een miljard (stelling 3). De tabel rekent elke deelvraag precies één keer uit; daar zit de winst.
Wordt de capaciteit zelf gigantisch, een miljoen bijvoorbeeld, dan wordt de tabel ook zo breed. Dan zijn er andere trucs nodig, maar voor de meeste echte problemen is de tabel ruim genoeg.
Klaar met voorspellen? Tijd voor de eerste regel Python.
Door naar items in Python →.