Ga naar hoofdinhoud

Het complete algoritme

Leerdoel: je combineert de 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 = []
    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]
  1. Regel 3-5:

    Bouwsteen 2 — de lege tabel: (n + 1) rijen van (capaciteit + 1) nullen. De extra rij is "geen items", de extra kolom "geen ruimte".

  2. Regel 7-8:

    Bouwsteen 4 — rij voor rij; items[i - 1] omdat rij 1 over het eerste item gaat en Python vanaf 0 telt.

  3. Regel 10-11:

    Past het item niet in capaciteit w? Kopieer dan de cel erboven: zonder dit item verandert er niets.

  4. Regel 12-15:

    Bouwsteen 3 — de kern: skip (cel erboven) tegen meenemen (waarde plus de beste vulling van de rest), en de grootste van de twee wint.

  5. Regel 17:

    De eindcel: de beste totaalwaarde voor alle items binnen de volle capaciteit.

Vergelijk met de tabel die je bij vul de tabel in met de hand invulde: ze horen identiek te zijn.

Voorspel​

We runnen knapsack op het voorbeeld van de les (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 met de hand uitrekende.

Run​

Python
Code-omgeving wordt voorbereid…
Verwachte uitvoer
Voorbeeld van de les:
    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 = 56
    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…
Antwoord
  1. Dat hangt van het item af. Haal je item 3 (18, 5) weg, dan zakt de beste waarde naar 35: items 1, 2 en 5 (1 + 6 + 28, gewicht 10). Haal je item 5 weg, dan blijft het 40, want die zat er toch niet in.
  2. Nee: een item van 1000 kg past in geen enkele kolom, dus elke cel in zijn rij kopieert de cel erboven. De tabel wordt er wel een stuk breder van: capaciteit + 1 kolommen blijft 12, maar had je knapsack(items, 1000) gevraagd, dan waren het er 1001.
  3. 31 × 101 = 3131 cellen.

Visualiseer de groei​

Beste waarde als functie van rugzakcapaciteit:

Python
Code-omgeving wordt voorbereid…
Wat zie je?

Een trap: de beste waarde stijgt in sprongen, telkens als de capaciteit groot genoeg wordt voor een nieuw item. Bij W=21 zit je op het maximum (75), want dan passen alle items.

Door naar welke items? →.