Ga naar hoofdinhoud

10.8 Het complete algoritme

Leerdoel: je combineert de drie bouwstenen in één functie knapsack(items, capaciteit) die de tabel bouwt en de beste totaalwaarde returnt.

Alles samen​

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]

Zie je de bouwstenen?

  • Regel 3 → bouwsteen 2: lege tabel maken.
  • Regels 5-13 → bouwsteen 3+4: rij voor rij invullen volgens de drie regels (te zwaar → kopieer, anders → max).
  • Regel 15 → eindcel returnen.

Vergelijk met de hand-uitgevulde tabel uit pagina 02: ze zouden identiek moeten zijn.

Voorspel​

We runnen knapsack op het image-voorbeeld (5 items, W=11). Wat denk je dat eruit komt?

Antwoord

40 — items 3 + 4 (waardes 18 + 22), gewicht 5 + 6 = 11.

Identiek aan wat je op pagina 02 met de hand uitrekende.

Run​

Python
Code-omgeving wordt voorbereid…
Verwachte uitvoer
Image-voorbeeld:
  knapsack(items, 11) = 40

Andere capaciteiten:
  W =  5  ->  beste waarde = 18
  W =  8  ->  beste waarde = 29
  W = 11  ->  beste waarde = 40
  W = 15  ->  beste waarde = 51
  W = 21  ->  beste waarde = 75
  • W=5: één item past — item 3 (waarde 18).
  • W=11: items 3+4 = 40 (zoals de tabel).
  • W=21: pak ze allemaal — 1+6+18+22+28 = 75, gewicht 21.

Onderzoek​

Speel met de code. Probeer:

  1. Verwijder een item: wat gebeurt er met de beste totaalwaarde?
  2. Voeg een item toe met waarde 100 en gewicht 1000: heeft die invloed?
  3. Hoe groot wordt de tabel als n = 30 en W = 100? (Hint: (n+1) × (W+1).)
Python
Code-omgeving wordt voorbereid…

Visualiseer de groei​

Beste waarde als functie van rugzakcapaciteit:

Python
Code-omgeving wordt voorbereid…
Wat zie je?

Een trap-vorm: de beste waarde stijgt in sprongen telkens als de capaciteit groot genoeg wordt om een nieuw item toe te voegen. Bij W=21 zit je op het maximum (75) — alle items passen.

Door naar stap 9: welke items? →.