Om contant betalingsverkeer mogelijk te maken, worden geldbriefjes en muntstukken uitgegeven. De toegelaten waarde van die briefjes en munten wordt vastgelegd via een rij gehele getallen. Per object van de te programmeren klasse MuntProbleem houden we per toegelaten waarde een aatal munten/briefjes bij. Bij aanmaak van een object van de klasse MuntProbleem is het aantal beschikbare munten en briefjes 0 (m.a.w. de portefeuille is leeg ...).

Programmer in de klasse MuntProbleem het volgende:

• een constructor met 1 argument, namelijk de lijst w met toegelaten waarden van munten en briefjes. Deze lijst bevat enkel strikt positieve gehele getallen, bevat geen dubbels, en is opklimmend gesorteerd.
• de operator += heeft als rechteroperand een tuple van 2 gehele getallen. Het eerste getal geeft een aantal briefjes of muntstukken aan, het tweede getal geeft de waarde van het desbetreffende briefje of muntstuk aan (het tuple (3, 5) geeft dus 3 briefjes/munten aan met waarde 5).
  • indien het rechteroperand geen tuple is, of geef geldig tuple is (verkeerd aantal componenten of componenten geen geheel getal, dan heeft de operator geen effect
  • Indien het om een niet-geldige waarde gaat m.b.t. de waarde van het briefje of muntstuk, dan heeft de operator geen effect.
  • Indien het om een geldige waarde gaat van het briefje of muntstuk, en het om een geldig rechteroperand gaat, dan is de werking als volgt:
    • indien het om een positief aantal gaat, wordt dit aantal briefjes/muntstukken van die waarde toegevoegd aan het object
    • indien het om een negatief aantal gaat, wordt dit aantal briefjes/muntstukken verwijderd uit het object, als dit mogelijk is. Indien je hierdoor op een negatief aantal briefjes/muntstukken van die waarde zou bekomen, dan gaat de hele operatie niet door. De volledige +=-opdracht wordt dus genegeerd en heeft GEEN effect.
• de methode __str__() levert een stringgedaante. Hiertoe gebruik je de standaarstringgedaante van een lijst die uit tuples bestaat, waarbij elk tuple een koppel gehele getallen voorstelt. Het eerste getal van elk tuple is een aantal briefjes/muntstukken en het tweede getal is de bijhorende waarde. Zorg dat elke waarde precies 1 keer voorkomt in de stringgedaante en dat de tuples gesorteerd zijn volgens opklimmende waarde. Neem voor elk tuple de standaardstringgedaante.
• de methode betaal_gulzig() heeft één strikt positief geheel argument, dat een bedrag voorstelt. Het is de bedoeling om dit bedrag uit te tellen via een aantal muntstukken en biljetten met geldige waarden, waarbij je geen rekening hoeft te houden met het aantal beschikbare munten/briefjes (je mag dus veronderstellen dat je in principe een onbeperkte hoeveelheid briefjes/munten van elke waarde ter beschikking hebt). Construeer de unieke oplossing die zoveel mogelijk briefjes/munten met grote waarden gebruikt. Start dus met de grootste coupure, en ga na hoeveel munten/briefjes van die waarde je kan gebruiken. Ga verder met de op één na grootste coupure voor het overblijvende bedrag. Ga zo verder tot je alle waarden nagekeken hebt. Je mag ervan uitgaan dat er op die manier voor de gegeven testen steeds één geldige oplossing kan gevonden worden. Het resultaat is een tuple, met per element het aantal munten/briefjes dat je gebruikt hebt, waarbij het element op positie i dus aangeeft hoeveel munten/briefjes met waarde w[i] je gebruikt hebt.
• de methode betaal() heeft eveneens één argument, namelijk een bedrag. Opnieuw ga je ervan uit dat je een onbeperkte hoeveelheid ter beschikking hebt van elke coupure. Nu genereer je ALLE oplossingen die het bedrag realiseren, waarbij elke oplossing als tuple van gehele getallen voorgesteld wordt (interpretatie identiek als hierboven). Het resultaat van de methode is een lijst die alle oplossingen bevat.
• de methode betaal_budget() heeft opnieuw een bedrag als enig argument, en levert opnieuw een lijst van alle oplossingen op om het bedrag te realiseren, maar nu rekening houdend met het aantal coupures dat beschikbaar is.

Voorbeeld

Tabblad 1

m = MuntProbleem([2, 6, 9])
m += (7, 2)
print(m) #[(7, 2), (0, 6), (0, 9)]
m += (8, 2)
print(m) #[(15, 2), (0, 6), (0, 9)]

for a in [('ab', 6), (5, 2), (4, 3), [1, 5], (9, 6)]:
	m += a
print(m) #[(20, 2), (9, 6), (0, 9)]

m = MuntProbleem([3, 4])
m += (3, 2)
print(m) #[(0, 3), (0, 4)]
m += 'a'
print(m) #[(0, 3), (0, 4)]

for a in [1, [1, 5], (9, 4), (7, 3), (10, 3)]:
	m += a
print(m) #[(17, 3), (9, 4)]

Tabblad 2

m = MuntProbleem([1, 2, 5, 8])
print(m.betaal_gulzig(37)) #(0, 0, 1, 4)

m = MuntProbleem([1, 2, 5, 8])
print(m.betaal_gulzig(66)) #(0, 1, 0, 8)

Tabblad 3

m = MuntProbleem([3, 7, 10])
for a in [(5, 3), (10, 10), (10, 3), (7, 7), (3, 3), (5, 10), (1, 7), (7, 7)]:
	m += a
print(m) #[(18, 3), (15, 7), (15, 10)]
print(sorted(m.betaal(60))) #[(0, 0, 6), (1, 1, 5), (2, 2, 4), (3, 3, 3), (4, 4, 2), (5, 5, 1), (6, 6, 0), (10, 0, 3), (11, 1, 2), (12, 2, 1), (13, 3, 0), (20, 0, 0)]
print(sorted(m.betaal_budget(60))) #[(0, 0, 6), (1, 1, 5), (2, 2, 4), (3, 3, 3), (4, 4, 2), (5, 5, 1), (6, 6, 0), (10, 0, 3), (11, 1, 2), (12, 2, 1), (13, 3, 0)]

m = MuntProbleem([2, 5, 8])
for a in [(4, 8), (2, 2), (7, 5), (1, 8), (4, 8), (9, 8), (5, 5), (8, 2)]:
	m += a
print(m) #[(10, 2), (12, 5), (18, 8)]
print(sorted(m.betaal(33))) #[(0, 5, 1), (1, 3, 2), (2, 1, 3), (4, 5, 0), (5, 3, 1), (6, 1, 2), (9, 3, 0), (10, 1, 1), (14, 1, 0)]
print(sorted(m.betaal_budget(33))) #[(0, 5, 1), (1, 3, 2), (2, 1, 3), (4, 5, 0), (5, 3, 1), (6, 1, 2), (9, 3, 0), (10, 1, 1)]