14.5 Pak de rugzak in
Vier items, een rugzak die 8 kilo draagt. Welke combinatie is het meeste waard? Je gokt eerst op gevoel, en rekent het daarna exact uit met de tabel-methode van het knapsack-algoritme.
Wat je nodig hebt
- Een geprinte hand-out, een schaar en een potlood per tweetal.
- Ongeveer 25 minuten.
De items
Knip de vier kaartjes uit:
Item 1
waarde: 3
gewicht: 2 kg
Item 2
waarde: 7
gewicht: 3 kg
Item 3
waarde: 9
gewicht: 4 kg
Item 4
waarde: 12
gewicht: 6 kg
De rugzak draagt maximaal 8 kg. Elk item is er maar één keer (meenemen of laten liggen — vandaar "0/1").
Gok eerst
Leg zonder te rekenen de kaartjes die jij zou meenemen bij elkaar. Schrijf op: items ____, totale waarde ____, totaal gewicht ____ kg.
De meeste mensen pakken eerst het waardevolste item. Onthoud je gok — straks zie je of dat slim was.
De tabel
Vul de tabel rij voor rij in. Elke cel beantwoordt: "wat is de beste waarde als ik alleen de items t/m deze rij mag gebruiken en zóveel kilo draagkracht heb?" Per cel zijn er drie mogelijkheden:
- Rij 0 (geen items): altijd 0 — al ingevuld.
- Past het item van deze rij niet (te zwaar voor deze kolom)? Kopieer de cel er recht boven.
- Past hij wel? Vergelijk overslaan (cel recht boven) met meenemen (waarde van het item + de cel één rij hoger en het gewicht van het item aan kolommen naar links). Schrijf de hoogste op.
| beste waarde | 0 kg | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| geen items | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| t/m item 1 (3, 2 kg) | 0 | ||||||||
| t/m item 2 (7, 3 kg) | 0 | ||||||||
| t/m item 3 (9, 4 kg) | 0 | ||||||||
| t/m item 4 (12, 6 kg) | 0 |
De cel rechtsonder is de beste totaalwaarde. Beter dan je gok?
Teruglopen — welke items?
De tabel geeft het getal, niet de items. Loop terug vanaf rechtsonder, rij voor rij omhoog:
- Is de cel gelijk aan de cel erboven? Dan is het item van deze rij niet meegenomen. Ga een rij omhoog, zelfde kolom.
- Is hij hoger? Dan zit het item erin. Leg dat kaartje bij je rugzak en ga een rij omhoog én het gewicht van het item aan kolommen naar links.
Schrijf op: items ____, waarde ____, gewicht ____ kg.
Bespreek na
- Zat het waardevolste item (item 4) in de beste rugzak? Waarom kan "pak steeds het waardevolste" verliezen van de tabel?
- Hoeveel kilo bleef er ongebruikt? Mag een optimale rugzak ruimte overhouden?
Antwoorden
Deze pagina print als losse laatste pagina — houd hem achter de hand of knip hem eraf.
| beste waarde | 0 kg | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| geen items | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| t/m item 1 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| t/m item 2 | 0 | 0 | 3 | 7 | 7 | 10 | 10 | 10 | 10 |
| t/m item 3 | 0 | 0 | 3 | 7 | 9 | 10 | 12 | 16 | 16 |
| t/m item 4 | 0 | 0 | 3 | 7 | 9 | 10 | 12 | 16 | 16 |
Beste rugzak: items 2 en 3, waarde 16, gewicht 7 kg (1 kg blijft over — dat mag).
Wie gretig het waardevolste item pakt komt op items 4 en 1 uit: waarde 15. Item 4 is in zijn eentje veel waard, maar bezet zóveel ruimte dat de sterkere combinatie 2 + 3 niet meer past. Daarom rekent het algoritme alle deelproblemen door in plaats van hebberig te kiezen.
De onderste twee rijen zijn identiek: dat betekent "item 4 voegt niets toe", en dat is precies hoe het teruglopen ziet dat item 4 niet mee is.
Verder op de site
- 10.1 Knapsack — het idee
- 10.2 Vul de tabel in — dezelfde methode op een groter voorbeeld, stap voor stap voorgedaan
- 10.4 Bouwen — daarna bouw je de tabel in Python