Ga naar hoofdinhoud

10.6 Bouwsteen 3 — vul één rij in

Leerdoel: je schrijft de logica die voor één rij i alle cellen OPT(i, w) invult, volgens de drie regels uit pagina 02.

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. We muteren tabel ter plekke — rij i is na de aanroep ingevuld.

Voorspel​

We hebben rij 0 al klaar (allemaal 0). Wat moet er in rij 1 staan voor het image-voorbeeld (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 pagina 02.

Bouw zelf en test​

Python
Code-omgeving wordt voorbereid…
Tip
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)

Let op:

  • items[i - 1] — i is 1-gebaseerd (rij-nummer in de tabel), maar Python-lijsten zijn 0-gebaseerd, dus -1.
  • range(capaciteit + 1) — vergeet +1 niet, anders mis je kolom w = capaciteit.
  • meenemen gebruikt tabel[i - 1][w - gewicht] — terugkijken in de vorige rij, gewicht kolommen naar links.

Wat nu nog mist​

Eén rij invullen werkt. Voor het complete algoritme moeten we dat voor alle rijen herhalen — dat is een extra for-lus eromheen.

Door naar stap 7: vul de hele tabel →.