Gegeven zijn een reeks munten met verschillende waardes, bijvoorbeeld 1, 2, 5, 10, 20 en 50 cent. Ontwerp en implementeer een algoritme dat via dynamisch programmeren berekent hoe een gegeven bedrag kan samengesteld worden met een minimale selectie van beschikbare munten. Er is altijd een munt van waarde 1 beschikbaar, zodat elk mogelijk bedrag gevormd kan worden.

Voorbeelden

Neem de munten zoals hierboven: 1, 2, 5, 10, 20 en 50 cent. Dan kunnen we deze gebruiken om volgende bedragen te bekomen met een minimum aan muntstukken:

• De beste manier om het bedrag 120 te vormen is door 2 munten van waarde 50 en 1 van waarde 20 te combineren.
• Het bedrag 79 vormen we best met 1 munt van 50, 1 van 20, 1 van 5, en 2 van 2.
• Het bedrag 33 tenslotte kunnen we met een minimum aan munten vormen wanneer we een munt van waarde 20, 10, 2 en 1 samenleggen.

Om dit probleem op te lossen, schrijf je een klasse DynamischWisselgeld die de gegeven interface Wisselgeld¹ implementeert. Deze bevat een methode public Map<Integer, Integer> wisselgeld(Collection<Integer> munten, int bedrag), die de samenstelling van het bedrag met een minimaal aantal muntstukken bepaalt via dynamisch programmeren. Als input krijgt deze methode een lijst van de beschikbare munten en het te vormen bedrag mee. Als output geeft deze een Map terug die elke gebruikte muntwaarde afbeeldt op het aantal van deze munten dat gebruikt wordt om het bedrag te vormen. Indien een muntstuk niet wordt gebruikt, kan deze aan de Map worden toegevoegd met waarde 0 of kan deze uit de Map weggelaten worden.

Opmerkingen

• Pas de inputlijst niet aan. Indien je dit wel doet, zullen de testen falen.
• Voeg enkel munten toe aan de Map die in de inputlijst aanwezig zijn.
• Alle waarden in de Map moeten positief zijn.

Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.