Cheatsheet — Knapsack 0/1

Snelle referentie. Klap open wat je nodig hebt.

Het algoritme zelf

De implementatie: de tabel van dit hoofdstuk

def knapsack(items, capaciteit):
    n = len(items)
    tabel = []
    for _ in range(n + 1):
        tabel.append([0] * (capaciteit + 1))
    for i in range(1, n + 1):
        waarde, gewicht = items[i - 1]
        for w in range(capaciteit + 1):
            if gewicht > w:
                tabel[i][w] = tabel[i - 1][w]
            else:
                skip = tabel[i - 1][w]
                meenemen = waarde + tabel[i - 1][w - gewicht]
                tabel[i][w] = max(skip, meenemen)
    return tabel[n][capaciteit]

Welke items? (backtrack uit tabel)

def knapsack_items(items, capaciteit):
    n = len(items)
    tabel = []
    for _ in range(n + 1):
        tabel.append([0] * (capaciteit + 1))
    for i in range(1, n + 1):
        waarde, gewicht = items[i - 1]
        for w in range(capaciteit + 1):
            if gewicht > w:
                tabel[i][w] = tabel[i - 1][w]
            else:
                tabel[i][w] = max(tabel[i - 1][w], waarde + tabel[i - 1][w - gewicht])

    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 keuze

De formule

De wiskundige formule

            ⎧ 0                                       als i = 0
OPT(i, w) = ⎨ OPT(i-1, w)                              als wᵢ > w
            ⎩ max{ OPT(i-1, w), vᵢ + OPT(i-1, w - wᵢ) } anders

De drie regels van vul de tabel in, als één formule. De Python-functie vult ze in van linksboven naar rechtsonder in de tabel.

De bouwstenen

1. Items als (waarde, gewicht) tuples

items = [(1, 1), (6, 2), (18, 5), (22, 6), (28, 7)]
waarde, gewicht = items[i - 1]

Python-indexen starten op 0; tabel-rijen starten op 1 (rij 0 = geen items). Conversie: items[i - 1].

2. Lege tabel

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

(n + 1) × (capaciteit + 1) — vergeet de +1 niet.

3. Eén rij invullen

waarde, gewicht = items[i - 1]
for w in range(capaciteit + 1):
    if gewicht > w:
        tabel[i][w] = tabel[i - 1][w]
    else:
        tabel[i][w] = max(tabel[i - 1][w], waarde + tabel[i - 1][w - gewicht])

Regel 2 en 3 van de formule: te zwaar, of het maximum.

4. Alle rijen — buitenste lus

for i in range(1, n + 1):
    # vul rij i

range(1, n + 1) — start bij 1 (rij 0 is al klaar), eindigt op n.

5. Backtrack — welke items?

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 keuze

Van n omlaag naar 1. Bij verschil tussen (i, w) en (i-1, w) is item i meegenomen — index opslaan én w verminderen.

Eigenschappen

Wat lost knapsack 0/1 op?

Werkt op	Werkt niet op
Items met gehele gewichten en waardes	Items in halve hoeveelheden (gebruik fractional knapsack)
Capaciteit ≥ 0	Negatieve capaciteit (zinloos)
0/1 keuze per item	Onbeperkte voorraad per item (gebruik unbounded knapsack)

Complexiteit

Versie	Tijd	Ruimte
De tabel van dit hoofdstuk	O(n × W)	O(n × W)
Naïeve recursie (zonder cache)	O(2ⁿ)	O(n)
Recursie met een cache (memoization)	O(n × W)	O(n × W)

n × W is voor 100 items en W=1000 zo'n 100.000 cellen — fracties van een seconde op een laptop. Het algoritme schaalt prima voor de meeste echte problemen.

Zie Big O notatie voor uitleg van die termen.

Top-3 valkuilen

Veelgemaakte fouten

1. Off-by-one in tabel-grootte: (n + 1) × (W + 1), niet n × W.
2. i-loop start bij 0: rij 0 is al klaar. Begin bij i = 1.
3. Backtrack vergeet w te verminderen bij meegenomen item → verkeerde lijst van items.

Volledig overzicht: er gaat iets mis.

Bonus — een recursieve variant

Hetzelfde probleem, top-down

Je kunt knapsack ook recursief schrijven: van het hele probleem naar de kleinere deelproblemen, in plaats van de tabel van klein naar groot. De drie regels zijn dezelfde; het verschil zit in de richting:

def knapsack_recursief(items, capaciteit, n):
    if n == 0 or capaciteit == 0:
        return 0
    waarde, gewicht = items[n - 1]
    if gewicht > capaciteit:
        return knapsack_recursief(items, capaciteit, n - 1)
    skip = knapsack_recursief(items, capaciteit, n - 1)
    meenemen = waarde + knapsack_recursief(items, capaciteit - gewicht, n - 1)
    return max(skip, meenemen)

Compact, maar zonder cache rekent hij dezelfde deelproblemen keer op keer uit: O(2ⁿ). Voor grote invoer is de tabel dus veel sneller.

Verder lezen

• het idee — opnieuw door het concept.
• vul de tabel in — het algoritme zélf uitgevoerd met de hand.
• het complete algoritme — alles samen, met plot van waarde-vs-capaciteit.
• Big O notatie — O(n × W) versus O(2ⁿ).