Ga naar hoofdinhoud

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 meeneemt, door de tabel terug te lopen zoals je bij vul de tabel in met de hand deed.

Wat we willen​

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

Het idee — backtrack door de tabel​

Bij vul de tabel in 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

Achteruit lopen doe je met range(n, 0, -1): dat geeft n, n-1, …, 1. Drie dingen om op te letten:

  1. i is de rij in de tabel (vanaf 1), i - 1 de index in items.
  2. Vergelijk tabel[i][w] met de cel erboven, tabel[i - 1][w].
  3. Vergeet w -= ... niet als het item is meegenomen — anders blijf je in dezelfde kolom hangen en raakt de backtrack van slag.
Antwoord
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
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=6

Dezelfde items als met de hand. De backtrack in Python doet precies wat jij op papier deed.

Door naar bouw zelf →.