Ga naar hoofdinhoud

Bouwsteen 3 — vul één rij in

Hier bouw je op verder

Leerdoel: je schrijft de logica die voor één rij i alle cellen OPT(i, w) invult, volgens de drie regels van vul de tabel in.

Wat we willen​

Gegeven:

  • de items-lijst,
  • een tabel met rijen 0 t/m i-1 al ingevuld,
  • het rij-nummer i dat we nu willen invullen.

Vul alle cellen van rij i in, voor w = 0 t/m W (capaciteit).

De drie regels (herhaling)​

Voor elke cel (i, w):

  1. Als gewicht > w (item past niet): tabel[i][w] = tabel[i-1][w].
  2. Anders: tabel[i][w] = max(skip, meenemen) waarbij:
    • skip = tabel[i-1][w]
    • meenemen = waarde + tabel[i-1][w - gewicht]

Kolom w = 0 is per definitie 0 (lege rugzak), maar als we range(W + 1) gebruiken vult onze code dat ook netjes in via dezelfde regels.

Specificatie​

  • Input: tabel, items, i (huidige rij), capaciteit.
  • Output: niets. De functie verandert tabel zelf; na de aanroep is rij i ingevuld.

Voorspel​

We hebben rij 0 al klaar (allemaal 0). Wat moet er in rij 1 staan voor het voorbeeld van de les (item 1 = waarde 1, gewicht 1)?

Antwoord

[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

  • w=0: item past niet (gewicht 1 > 0) → kopieer tabel[0][0] = 0.
  • w=1 t/m w=11: item past. Skip = tabel[0][w] = 0. Meenemen = 1 + tabel[0][w-1] = 1. → max = 1.

Klopt met de tabel van vul de tabel in.

Bouw zelf en test​

Python
Code-omgeving wordt voorbereid…
Tip

Het commentaar in de starter is bijna de code. Drie dingen om op te letten:

  • items[i - 1] — i is het rijnummer in de tabel (vanaf 1), maar Python-lijsten tellen vanaf 0, dus -1.
  • range(capaciteit + 1) — vergeet +1 niet, anders mis je kolom w = capaciteit.
  • meenemen kijkt in de vorige rij, gewicht kolommen naar links: tabel[i - 1][w - gewicht].
Antwoord
def vul_rij(tabel, items, i, capaciteit):
    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)

Regel 2 is de if, regel 3 de else. Regel 1 (rij 0) hoeft niet: die staat al vol nullen.

Wat nu nog mist​

Eén rij invullen werkt. Voor het complete algoritme herhaal je dat voor alle rijen: een extra for-lus eromheen.

Door naar vul de hele tabel →.