10.10 Bouw zelf — de hike-rugzak
Leerdoel: je past de tabel-aanpak toe op een nieuw scenario: een trekking-rugzak met 6 items en gewichtslimiet 15 kg.
Opdracht
Je gaat 4 dagen wandelen. In je rugzak past 15 kg. Voor je liggen deze items, elk met een "nuttigheids-score" (waarde) en gewicht:
| Item | Wat | Waarde | Gewicht |
|---|---|---|---|
| 1 | Slaapzak | 12 | 4 |
| 2 | Tent | 18 | 7 |
| 3 | Kookstel | 8 | 3 |
| 4 | Waterfilter | 10 | 2 |
| 5 | Eten (3 dagen) | 14 | 5 |
| 6 | Powerbank | 6 | 1 |
Bouw een functie kies_rugzak(items, capaciteit) die teruggeeft:
- de totale waarde,
- de lijst met Python-indexen van de meegenomen items.
Tip
Bouw de tabel inline en backtrack erover:
def kies_rugzak(items, capaciteit):
n = len(items)
tabel = [[0] * (capaciteit + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
v, g = items[i - 1]
for w in range(capaciteit + 1):
if g > w:
tabel[i][w] = tabel[i - 1][w]
else:
tabel[i][w] = max(tabel[i - 1][w], v + tabel[i - 1][w - g])
# Backtrack
keuze = []
w = capaciteit
for i in range(n, 0, -1):
if tabel[i][w] != tabel[i - 1][w]:
keuze.append(i - 1)
w -= items[i - 1][1]
return tabel[n][capaciteit], keuze
Verwacht antwoord
Beste combinatie: items 1, 3, 4, 5, 6 (alles behalve de tent).
- Waarde: 12 + 8 + 10 + 14 + 6 = 50
- Gewicht: 4 + 3 + 2 + 5 + 1 = 15 (precies op de limiet)
De tent is met gewicht 7 zó duur dat hij meerdere kleinere items verdringt. Pak je hem mee, dan kun je nog hoogstens 8 kg aan andere items kwijt — dat geeft maximum 48.
Uitdaging (optioneel)
Voeg een 7e item toe — een verrekijker met waarde 4 en gewicht 1. Verandert de optimale keuze?
Wat heb je nu geleerd?
Je hebt het klassieke knapsack-probleem in zijn DP-tabel-vorm gebouwd, getest, en toegepast op een echt scenario. De tabel-aanpak schaalt naar veel grotere problemen dan met de hand zou kunnen — en de backtrack-procedure haalt er de items uit.
Door naar stap 11: veelgemaakte fouten →.