Knapsack 0/1 — het idee
Leerdoel: je begrijpt wat het 0/1 knapsack-probleem is en wat de "0/1" betekent. Nog geen code.
Het verhaal
Je gaat hiken. In je rugzak past maar 11 kg. Voor je liggen een paar items met elk een waarde (hoe nuttig in de natuur) en een gewicht (hoe zwaar):
| Item | Waarde | Gewicht | Waarde per kg |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 6 | 2 | 3 |
| 3 | 18 | 5 | 3,6 |
| 4 | 22 | 6 | 3,7 |
| 5 | 28 | 7 | 4 |
Welke items neem je mee om je rugzak zo waardevol mogelijk te maken zonder boven de 11 kg te komen?
Niet zomaar zoveel mogelijk items, want sommige duwen je over de limiet. Sorteren helpt ook niet. Pak je de waardevolste eerst, dan neem je item 5 (7 kg), daarna past alleen item 2 en item 1 nog: waarde 35. Pak je de beste waarde per kilo eerst, dan begin je óók met item 5 (4 per kilo) en kom je op dezelfde 35 uit. De beste rugzak is 40 waard: items 3 en 4, samen precies 11 kg. Die combinatie vind je niet door items één voor één te beoordelen, hoe slim je ook sorteert.
Wat betekent "0/1"?
De 0/1 in de naam zegt: elk item neem je één keer mee (1), of helemaal niet (0). Niet halveren, niet twee keer meenemen, niet "een beetje" pakken. Er zijn varianten waarin dat wel mag, fractional knapsack en unbounded knapsack; die komen hier niet aan bod.
De aanpak — één vraag per item
Voor elk item is er maar één vraag: neem ik dit mee, of niet? Meer smaken zijn er niet, en met vijf items geeft dat 2⁵ = 32 combinaties.
Voor elke combinatie:
- Tel het totale gewicht. Past het binnen 11? Zo niet, sla over.
- Tel de totale waarde. Onthoud de hoogste tot nu toe.
32 combinaties is te doen. Bij 10 items zijn het er 1024, bij 20 meer dan een miljoen.
De tabel-truc
In plaats van alle 32 combinaties uit te proberen, vul je een tabel in van klein naar groot: één cel per combinatie van "items tot nu toe" en "beschikbare capaciteit". Voor elke cel reken je twee dingen uit: de beste waarde zonder dit item, en de beste waarde mét dit item. De grootste van de twee komt in de cel.
Bij elke nieuwe cel kijk je terug naar cellen die al ingevuld zijn, dus
je rekent niets twee keer uit. Voor 5 items en W=11 is dat een tabel
van 6 × 12 = 72 cellen, zo klaar.
Wat we gaan bouwen
Aan het eind van dit hoofdstuk schrijf je een Python-functie:
def knapsack(items, capaciteit):
...
die de tabel opbouwt en de eindcel tabel[n][capaciteit] teruggeeft:
de beste totaalwaarde. Daarna nog een functie die zegt wélke items dat
zijn, door de tabel terug te lopen.
Eerst met pen en papier. Je vult de tabel zelf in.
Zo bouw je het op
De code bouw je in kleine stappen, elk op een eigen pagina in de map "Bouwen, stap voor stap":
- Bouwsteen 1 — items in Python
- Bouwsteen 2 — een lege tabel
- Bouwsteen 3 — vul één rij in
- Bouwsteen 4 — vul de hele tabel
Daarna zet je alles samen in Het complete algoritme, en ga je het aanpassen en zelf bouwen.
Door naar vul de tabel in →.