Ga naar hoofdinhoud

10.9 Pas aan — welke items neem je mee?

Leerdoel: je breidt knapsack uit zodat hij niet alleen de beste totaalwaarde teruggeeft, maar ook welke items je daarvoor moet meenemen — via backtracking door de tabel, precies zoals je dat op pagina 02 met de hand deed.

Wat we willen​

Tot nu toe weten we: "de beste waarde is 40." Maar welke items? Antwoord: een lijst van indexen die je meeneemt. Voor het image- voorbeeld → [2, 3] (Python-indexen voor item 3 en 4).

Het idee — backtrack door de tabel​

Op pagina 02 leerde je: begin in cel (n, W) en loop naar boven. Voor elke rij i:

  • Als tabel[i][w] == tabel[i-1][w] → item i was niet nodig (skip wint). Ga naar (i-1, w).
  • Anders → item i was wel meegenomen. Ga naar (i-1, w - gewicht_i).

In Python is dat één for-loop van groot naar klein.

Specificatie​

  • Input: items, capaciteit.
  • Output: een lijst van Python-indexen van de meegenomen items.

Opdracht​

Python
Code-omgeving wordt voorbereid…
Tip
def knapsack_items(items, capaciteit):
    n = len(items)
    tabel = knapsack_tabel(items, capaciteit)

    keuze = []
    w = capaciteit
    for i in range(n, 0, -1):                # van n omlaag naar 1
        if tabel[i][w] != tabel[i - 1][w]:   # item i was meegenomen
            keuze.append(i - 1)              # 0-gebaseerde index
            w -= items[i - 1][1]             # capaciteit verminderen
    return keuze

Drie cruciale dingen:

  1. range(n, 0, -1) loopt n, n-1, ..., 1 — achteruit.
  2. i - 1 als Python-index (lijst-index), i als tabel-rij (1-gebaseerd).
  3. Vergeet w -= ... niet als item meegenomen is — anders blijf je in dezelfde kolom hangen en raakt de backtrack van slag.
Python
Code-omgeving wordt voorbereid…
Verwachte uitvoer
Indexen (Python): [2, 3]
Items (mens-nummering): [3, 4]
Totale waarde: 40
Totaal gewicht: 11 (van 11 toegestaan)

Details per item:
  item 3: waarde=18, gewicht=5
  item 4: waarde=22, gewicht=7

Exact dezelfde indices als je op pagina 02 met de hand uitkwam. De backtrack-procedure in Python is een 1-op-1 vertaling van wat je daar deed.

Wacht — item 4 weegt 6, niet 7. Klein typo in de verwachte uitvoer hierboven; werkelijke output zal gewicht=6 zijn. Test het zelf.

Door naar stap 10: bouw zelf →.