Er gaat iets mis — top-3 fouten

Leerdoel: je herkent de drie klassieke valkuilen bij de tabel-aanpak van knapsack.

Off-by-one in tabel-grootte

Foutmelding: IndexError: list index out of range of een tabel die te klein is.

Oorzaak: vergeet de +1 bij rijen of kolommen. De tabel heeft (n + 1) × (capaciteit + 1) cellen, niet n × capaciteit. Die extra rij is voor "geen items" (basisgeval); die extra kolom is voor "lege rugzak".

# FOUT
tabel = []
for _ in range(n):
    tabel.append([0] * capaciteit)

# Probleem: tabel[n][capaciteit] bestaat niet → crash bij return.

Oplossing:

# GOED
tabel = []
for _ in range(n + 1):
    tabel.append([0] * (capaciteit + 1))

Vuistregel: als je naar een cel [i][w] wilt kunnen met i = n én w = capaciteit, heb je n + 1 rijen en W + 1 kolommen nodig.

i-loop start bij 0

Geen foutmelding, wel een rij 0 die niet meer 0 is, en soms een totaalwaarde die te hoog is.

Oorzaak: rij 0 in de tabel is al ingevuld (basisgeval: allemaal 0). Je werkelijke "vul-rij"-werk start bij i = 1. Begin je bij i = 0, dan haal je items[-1] op, en Python's negatieve index geeft je het laatste item. Dat item komt zo in rij 0 terecht en kan daarna nog een keer meetellen: één item van waarde 10 en gewicht 1 in een rugzak van 2 geeft dan 20. Op het voorbeeld van de les komt er toevallig nog 40 uit, met een rij 0 vol 28'en.

# FOUT
for i in range(n + 1):       # start bij 0
    waarde, gewicht = items[i - 1]   # items[-1] = laatste item
    ...

Oplossing:

# GOED
for i in range(1, n + 1):    # start bij 1
    waarde, gewicht = items[i - 1]
    ...

Die 1 in range(1, n + 1) is het hele punt.

Backtrack vergeet capaciteit te verminderen

Geen foutmelding, wel een verkeerde lijst van items.

Oorzaak: bij elke "item meegenomen"-stap moet je niet alleen de index opslaan, maar ook de capaciteit verminderen met het gewicht van dat item. Vergeet je dat, dan blijf je naar dezelfde kolom kijken en lijken meer items "meegenomen" dan klopt.

# FOUT
for i in range(n, 0, -1):
    if tabel[i][w] != tabel[i - 1][w]:
        keuze.append(i - 1)
        # w wordt NIET aangepast → fout

Oplossing:

# GOED
for i in range(n, 0, -1):
    if tabel[i][w] != tabel[i - 1][w]:
        keuze.append(i - 1)
        w -= items[i - 1][1]    # cruciaal!

Je schuift naar links omdat dit item zijn gewicht al heeft ingenomen: er is minder capaciteit over voor de rest.

Door naar cheatsheet →.