Ga naar hoofdinhoud

10.12 Cheatsheet — Knapsack 0/1

Snelle referentie. Klap open wat je nodig hebt.

Het algoritme zelf​

De canonieke implementatie (bottom-up DP-tabel)
def knapsack(items, capaciteit):
    n = len(items)
    tabel = [[0] * (capaciteit + 1) for _ in range(n + 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 = [[0] * (capaciteit + 1) for _ in range(n + 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 recurrence​

De wiskundige formule (zoals in de docent's slides)
            ⎧ 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

Onze Python-functie vult deze drie regels 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 = [[0] * (capaciteit + 1) for _ in range(n + 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])

Twee regels uit de recurrence: te zwaar of max.

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 opWerkt niet op
Items met gehele gewichten en waardesItems in halve hoeveelheden (gebruik fractional knapsack)
Capaciteit ≥ 0Negatieve capaciteit (zinloos)
0/1 keuze per itemOnbeperkte voorraad per item (gebruik unbounded knapsack)
Complexiteit
VersieTijdRuimte
Bottom-up DP-tabel (deze track)O(n × W)O(n × W)
Naïeve recursie (zonder cache)O(2ⁿ)O(n)
Recursie + memoizationO(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: stap 11: er gaat iets mis.

Bonus — een recursieve variant​

Hetzelfde probleem, top-down

Je kunt knapsack ook recursief schrijven (top-down) in plaats van met een tabel (bottom-up). De recurrence is identiek; 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)

Mooi compact, maar zonder cache loopt het tijd op tot O(2ⁿ) — subproblemen worden vele keren herhaald. Voor grote inputs is de tabel-aanpak dus veel sneller.

Verder lezen​