Het wisselgeldprobleem

Een kassier die wisselgeld teruggeeft, pakt de grootste munt die past, dan de volgende, en voor euro's of dollars levert dat altijd de minste munten op. Maak de munten echter 1, 3 en 4, en dezelfde gewoonte betaalt 6 met drie munten terwijl twee genoeg zijn. Dynamisch programmeren vindt voor alle munten het echte minimum.

Een rij bedragen, elk met de minste munten die het vormen, boven munten van drie verschillende groottes
Een rij bedragen, elk met de minste munten die het vormen, boven munten van drie verschillende groottes

Twee vragen

Het wisselgeldprobleem bestaat in twee varianten. De eerste vraagt naar de minste munten voor een exact bedrag; dat heet ook wel het muntwisselprobleem. De tweede vraagt hoeveel verschillende combinaties van munten het bedrag vormen. In beide mag elke muntsoort zo vaak worden gebruikt als je wilt, en beide worden opgelost door het antwoord voor elk bedrag op te bouwen uit de antwoorden voor kleinere bedragen.

Minste munten, stap voor stap

Maak een rij cellen voor de bedragen van 0 tot het doel. Bedrag 0 kost 0 munten; elk ander bedrag begint op oneindig. Loop de bedragen op volgorde af en probeer voor elk bedrag elke munt c die past: de cel voor het bedrag min c, plus één munt, is een kandidaat. Houd de kleinste. Elke cel hangt alleen af van cellen links ervan, die al vaststaan, dus één doorgang vult de rij.

Een voorbeeld

Met munten 1, 3 en 4: bedrag 1 kost 1 munt, 2 kost er 2, 3 kost er 1 (één munt van 3) en 4 kost er 1. Voor 5 probeer je 1 (4 kost 1, dus 2 munten), 3 (2 kost 2, dus 3 munten) en 4 (1 kost 1, dus 2 munten): het beste is 2. Voor 6 probeer je 1 (5 kost 2, dus 3), 3 (3 kost 1, dus 2) en 4 (2 kost 2, dus 3): het beste is 2, met 3 + 3. Gretig had 4 + 1 + 1 betaald.

De manieren tellen

Om combinaties te tellen, voeg je de munten één voor één toe. Met alleen de eerste munt kan elk bedrag op één manier gevormd worden of helemaal niet. Komt er een nieuwe munt c bij, dan zijn de manieren om een bedrag a te vormen de oude manieren, zonder c, plus de manieren om a − c te vormen met c opnieuw toegestaan, want elk daarvan wordt een manier om a te vormen door er nog een c bij te doen. Met munten 1, 2 en 5 zijn er 4 manieren om 5 te vormen: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 en 1 + 1 + 1 + 1 + 1.

Wanneer gretig genoeg is

Een muntsysteem waarvoor gretig altijd de minste munten oplevert, heet canoniek. De meeste moderne valuta zijn zo ontworpen, en in 1994 beschreef David Pearson een test die een muntsysteem controleert in een aantal stappen dat maar polynomiaal groeit met het aantal munten. De oude Britse munten waren niet canoniek: gretig betaalt 48 pence als een halve kroon, een shilling en een sixpence, terwijl twee florijnen genoeg zijn.

Ontdek het zelf

Open de app, ga naar de weergave Tabel en druk op Stap. In de modus Minste munten is de oranje cel het bedrag dat wordt uitgerekend en de blauwe cel het kleinere bedrag dat de munt overlaat; de rij eronder bewaart de laatste munt, en aan het einde worden de munten langs die rij teruggelezen. Schakel over naar Aantal manieren en zie de aantallen rij voor rij groeien naarmate elke munt erbij komt.

Veelgestelde vragen

Is het wisselgeldprobleem een knapzakprobleem?

Een naaste verwant. De variant met de minste munten is een onbegrensd knapzakprobleem waarin elke munt een voorwerp is met de nominale waarde als gewicht, de knapzak precies gevuld moet worden en het doel zo min mogelijk voorwerpen is.

Wat is de tijdcomplexiteit?

O(k·A) voor k muntsoorten en een bedrag A, in beide varianten. De tabel voor de minste munten heeft A + 1 cellen, en de tabel voor de manieren (k + 1)·(A + 1), al is één rij genoeg als de cellen ter plekke worden bijgewerkt.

Waarom de munten in een vaste volgorde tellen?

Als elk bedrag elke munt zou proberen, zouden 1 + 2 en 2 + 1 als twee manieren worden geteld. Door de munten rij voor rij toe te voegen, wordt een combinatie altijd eerst uit de eerdere munten opgebouwd, zodat elke combinatie precies één keer wordt geteld.

Kun je de munten ook teruglezen voor het aantal manieren?

Niet als één antwoord, want het zijn er veel. De variant met de minste munten bewaart de laatste munt van elk bedrag, en dat is genoeg om één beste combinatie terug te vinden.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer wisselgeld