Bouw zelf — de hike-rugzak

Leerdoel: je past de tabel toe op een nieuwe situatie: een trekking-rugzak met 6 items en een limiet van 15 kg.

Opdracht

Je gaat 4 dagen wandelen. In je rugzak past 15 kg. Voor je liggen deze items, elk met een "nuttigheidsscore" (waarde) en gewicht:

Item	Wat	Waarde	Gewicht
1	Slaapzak	12	4
2	Tent	18	7
3	Kookstel	8	3
4	Waterfilter	10	2
5	Eten (3 dagen)	14	5
6	Powerbank	6	1

Bouw een functie kies_rugzak(items, capaciteit) die teruggeeft:

1. de totale waarde,
2. de lijst met Python-indexen van de meegenomen items.

Python

Code-omgeving wordt voorbereid…

Tip

Twee stukken die je al hebt: de tabel van het complete algoritme en de backtrack van welke items. Zet ze achter elkaar in één functie en geef aan het eind twee dingen terug, gescheiden door een komma: return tabel[n][capaciteit], keuze.

Antwoord

def kies_rugzak(items, capaciteit):
    n = len(items)
    tabel = []
    for _ in range(n + 1):
        tabel.append([0] * (capaciteit + 1))
    for i in range(1, n + 1):
        v, g = items[i - 1]
        for w in range(capaciteit + 1):
            if g > w:
                tabel[i][w] = tabel[i - 1][w]
            else:
                tabel[i][w] = max(tabel[i - 1][w], v + tabel[i - 1][w - g])

    # Backtrack
    keuze = []
    w = capaciteit
    for i in range(n, 0, -1):
        if tabel[i][w] != tabel[i - 1][w]:
            keuze.append(i - 1)
            w -= items[i - 1][1]

    return tabel[n][capaciteit], keuze

Beste combinatie: items 1, 3, 4, 5, 6 (alles behalve de tent).

• Waarde: 12 + 8 + 10 + 14 + 6 = 50
• Gewicht: 4 + 3 + 2 + 5 + 1 = 15 (precies op de limiet)

De tent is met gewicht 7 zó duur dat hij meerdere kleinere items verdringt. Pak je hem mee, dan kun je nog hoogstens 8 kg aan andere items kwijt — dat geeft maximum 48.

Uitdaging (optioneel)

Voeg een 7e item toe — een verrekijker met waarde 4 en gewicht 1. Verandert de optimale keuze?

Tip

Voeg (4, 1) toe aan de lijst en draai kies_rugzak opnieuw. Kijk naar de totale waarde én naar de lijst. Reken daarna met de hand na of er nóg een combinatie is die dezelfde waarde haalt.

Antwoord

De beste waarde blijft 50, en de functie geeft dezelfde vijf items terug. Toch is er nu een tweede rugzak van 50: slaapzak, tent, waterfilter, powerbank en verrekijker (12 + 18 + 10 + 6 + 4 = 50, gewicht 4 + 7 + 2 + 1 + 1 = 15).

Dat de functie de eerste kiest komt door de backtrack: bij een gelijkspel is de cel gelijk aan de cel erboven, en dat leest hij als "niet meegenomen". De verrekijker valt zo af, en de tent met hem.

Door naar veelgemaakte fouten →.