Use it or lose it

Deze pagina bevat uitvoerbare code.

Het vorige college sloot af met een vraag. In je portemonnee zitten drie munten: 20 cent, 50 cent en nog eens 50 cent. Kun je precies 70 cent betalen? En 80 cent?

Bij elke munt heb je een keuze: je gebruikt hem, of je gebruikt hem niet. In dit college leer je hoe je met recursie beide keuzes uitprobeert. Die aanpak heet use it or lose it: gebruik het element, of laat het liggen.

Eén tak of twee

In het vorige college had elk recursief geval één recursieve aanroep. Ook keepvwl en largest maakten een keuze, maar de functie wist steeds vooraf welke kant ze op moest. Is het eerste teken een klinker, dan hou je het; anders laat je het weg. Er werd maar één tak gevolgd.

Bij de munten weet je dat niet vooraf. Of je de munt van 20 cent moet gebruiken, hangt af van wat je met de rest kunt betalen. Daarom probeer je beide:

  • Use it. Je gebruikt de eerste munt. Dan moet je met de rest van de munten nog het bedrag min die munt betalen.

  • Lose it. Je laat de eerste munt liggen. Dan moet je met de rest van de munten het hele bedrag betalen.

Dat zijn twee recursieve aanroepen, elk op een kleiner probleem: een lijst met één munt minder.

Precies betalen: exact_change(amount, coins)

exact_change(amount, coins) geeft True als je het bedrag amount precies kunt betalen met een deel van de munten in de lijst coins, en anders False. Bedragen en munten zijn in centen.

Plan

  • Basisgeval. Er zijn er drie. Is het bedrag 0, dan heb je alles betaald: .... Is het bedrag kleiner dan 0, dan heb je te veel betaald: .... En zijn er geen munten meer terwijl er nog iets te betalen is, dan lukt het niet: ....

  • Kleiner probleem. De lijst zonder de eerste munt: coins[1:].

  • Combineren. Use it is exact_change(amount - coins[0], coins[1:]). Lose it is exact_change(...). Het lukt als een van de twee lukt.

Programmeren

def exact_change(amount, coins):
    """Geeft True als je amount precies kunt betalen met munten uit coins."""
    if amount == 0:  # basisgeval: alles is betaald
        return ...
    elif amount < 0:  # basisgeval: te veel betaald
        return ...
    elif coins == []:  # basisgeval: geen munten meer
        return ...
    else:  # recursief geval: probeer beide keuzes
        use_it = ...
        lose_it = ...
        return ...

Oplossing

def exact_change(amount, coins):
    """Geeft True als je amount precies kunt betalen met munten uit coins."""
    if amount == 0:  # basisgeval: alles is betaald
        return True
    elif amount < 0:  # basisgeval: te veel betaald
        return False
    elif coins == []:  # basisgeval: geen munten meer
        return False
    else:  # recursief geval: probeer beide keuzes
        use_it = exact_change(amount - coins[0], coins[1:])
        lose_it = exact_change(amount, coins[1:])
        return use_it or lose_it


assert exact_change(70, [20, 50, 50]) == True
assert exact_change(80, [20, 50, 50]) == False
assert exact_change(0, []) == True

Het antwoord op de vraag uit het vorige college: 70 cent kan, met 20 en 50 cent. 80 cent kan niet. Met 20 en 50 kom je op 70, met de twee munten van 50 op 100.

Het or aan het eind is de or van use it or lose it. Elke aanroep die niet in een basisgeval eindigt, doet zelf weer twee recursieve aanroepen. Zo probeert de functie alle manieren om munten te kiezen.

De knapzak

Kikker loopt met een knapzak aan een stok over zijn schouder

Kikker gaat op reis. In zijn knapzak kan hij spullen meenemen tot een maximaal gewicht. Hij wil de knapzak zo vol mogelijk maken, maar niet te zwaar.

Bij exact_change was het antwoord ja of nee. Nu zoek je het beste antwoord: de grootste som die niet boven de grens uitkomt. Dat heet ook wel het subset-sum-probleem: welke deelverzameling heeft de grootste som?

Een lastige keus

De knapzak kan 10 kilo dragen, en er liggen spullen van 8, 4 en 6 kilo:

capacity = 10
items = [8, 4, 6]

Hier kun je het eerste item beter niet meenemen. Laat je de 8 liggen, dan passen de 4 en de 6 samen precies.

Zet je dezelfde spullen in een andere volgorde, dan verandert de keus:

capacity = 10
items = [4, 8, 6]

Nu kun je het eerste item beter wel meenemen: de 4, en daarna de 6. De 8 laat je liggen.

Of je het eerste item moet gebruiken, hangt dus af van de rest. Je weet het pas als je beide keuzes hebt geprobeerd.

Probeer beide en kies de beste

  • Use it. Neem het eerste item mee. Dan heb je nog capacity - first over voor de rest: use_it = first + subset(capacity - first, rest).

  • Lose it. Laat het eerste item liggen: lose_it = subset(capacity, rest).

Van de twee kies je de grootste. Daarvoor heeft Python de ingebouwde functie max. Met twee argumenten geeft ze het grootste van de twee terug:

max(3, 8)

8

Eén geval vraagt nog aandacht. Is het eerste item zwaarder dan wat er nog in de knapzak past, dan kun je het niet meenemen. Dan blijft alleen lose it over.

Programmeren

def subset(capacity, items):
    """Geeft de grootste som van items die niet boven capacity uitkomt."""
    if items == []:  # basisgeval: geen items meer
        return ...

    first = items[0]
    rest = items[1:]

    if first > capacity:  # recursief geval: het eerste item past niet
        return ...
    else:  # recursief geval: probeer beide keuzes
        use_it = ...
        lose_it = ...
        return ...

Oplossing

def subset(capacity, items):
    """Geeft de grootste som van items die niet boven capacity uitkomt."""
    if items == []:  # basisgeval: geen items meer
        return 0

    first = items[0]
    rest = items[1:]

    if first > capacity:  # recursief geval: het eerste item past niet
        return subset(capacity, rest)
    else:  # recursief geval: probeer beide keuzes
        use_it = first + subset(capacity - first, rest)
        lose_it = subset(capacity, rest)
        return max(use_it, lose_it)


assert subset(10, [8, 4, 6]) == 10
assert subset(10, [4, 8, 6]) == 10
assert subset(42, [30, 10, 45, 5]) == 40
assert subset(10, []) == 0

Hoe werkt dit?

De figuur hieronder laat alle aanroepen zien van subset(42, [30, 10, 45, 5]). Elk vak is één aanroep, met de waarde van use it, lose it en wat de aanroep teruggeeft (ret). In de figuur heten de variabelen useit en loseit. Waar het eerste item niet past, staat drop: daar is alleen lose it geprobeerd.

De boom van alle aanroepen van subset(42, [30, 10, 45, 5]): elk vak toont de aanroep, de waarden van use it en lose it en het resultaat; de bovenste aanroep geeft 40 terug

Lees de boom van boven naar beneden en weer terug. De bovenste aanroep probeert eerst use it: de 30 mee, en dan nog 12 kilo voor [10, 45, 5]. Die tak geeft uiteindelijk 10 terug, dus use it is 30 + 10 = 40. Pas daarna komt lose it aan de beurt: de 30 laten liggen. Die tak geeft 15. Het grootste van de twee is 40.

Net als in het eerste college over recursie krijgt elke aanroep een eigen frame op de stack. Op het diepste punt staan er vijf frames van subset tegelijk: één per niveau in de boom. Een frame verdwijnt pas als zijn aanroep een antwoord heeft. Daarom staat lose it van de bovenste aanroep pas op de stack als de hele linkerhelft van de boom klaar is.

Opdrachten

Beantwoord bij elke opdracht eerst de drie vragen: wat is het basisgeval, wat is het kleinere probleem, en hoe combineer je? Probeer bij elk element beide keuzes.

Opdracht 1

Schrijf de functie count_ways(amount, coins). Die geeft terug op hoeveel manieren je amount precies kunt betalen met een deel van de munten in coins.

Aanroep

Resultaat

count_ways(10, [2, 3, 5, 7, 8])

3, want 2 + 8, 3 + 7 en 2 + 3 + 5

count_ways(80, [20, 50, 50])

0

count_ways(0, [])

1: niets betalen kan op één manier

Hint

De vorm is dezelfde als die van exact_change. Alleen combineer je de twee uitkomsten nu niet met or, maar tel je ze op.

# jouw oplossing

assert count_ways(10, [2, 3, 5, 7, 8]) == 3
assert count_ways(70, [20, 50, 50]) == 2
assert count_ways(80, [20, 50, 50]) == 0
assert count_ways(0, []) == 1
assert count_ways(5, []) == 0

Opdracht 2

Schrijf de functie most_items(capacity, items). Die geeft terug hoeveel items uit items je hoogstens kunt meenemen zonder boven capacity uit te komen. Het gaat nu om het aantal items, niet om hun som.

Aanroep

Resultaat

most_items(10, [8, 4, 6])

2

most_items(10, [3, 3, 3, 3])

3

most_items(5, [])

0

Hint

De vorm is dezelfde als die van subset. Bij use it tel je nu niet het gewicht van het item op, maar 1.

# jouw oplossing

assert most_items(10, [8, 4, 6]) == 2
assert most_items(10, [3, 3, 3, 3]) == 3
assert most_items(10, [6, 5, 4, 3]) == 2
assert most_items(5, []) == 0

Tot slot

Bij use it or lose it probeer je bij elk element twee dingen: je gebruikt het, of je laat het liggen. Dat zijn twee recursieve aanroepen. Hun uitkomsten combineer je, met or als je wilt weten of iets kan, met max als je het beste zoekt, en met + als je telt.

subset vertelt hoe vol de knapzak kan, maar niet wélke spullen erin gaan. Dat vraagt een max die niet twee getallen vergelijkt, maar twee lijsten met spullen, op hun som. Hoe je dat schrijft, zie je in het volgende college.