Byttepengeproblemet
En kasseassistent, der giver byttepenge, tager den største mønt, der passer, så den næste, og for euro eller dollar giver det altid færrest mønter. Men skift mønterne til 1, 3 og 4, og den samme vane betaler 6 med tre mønter, hvor to ville være nok. Dynamisk programmering finder det ægte minimum for alle mønter.
To spørgsmål
Byttepengeproblemet findes i to udgaver. Den første spørger efter det færreste antal mønter, der giver et præcist beløb; på engelsk kaldes den også the change-making problem. Den anden spørger, hvor mange forskellige kombinationer af mønter der giver beløbet. I begge må hver slags mønt bruges så mange gange, man vil, og begge løses ved at bygge svaret for hvert beløb op af svarene for mindre beløb.
Færrest mønter, trin for trin
Lav en række celler for beløbene fra 0 op til målet. Beløbet 0 kræver 0 mønter; alle andre beløb starter på uendelig. Gå beløbene igennem i rækkefølge, og prøv for hvert beløb hver mønt c, der passer: cellen for beløbet minus c, plus én mønt, er en kandidat. Behold den mindste. Hver celle afhænger kun af celler til venstre for den, som allerede er endelige, så én gennemgang fylder rækken.
Et eksempel
Med mønterne 1, 3 og 4: beløbet 1 kræver 1 mønt, 2 kræver 2, 3 kræver 1 (en enkelt 3'er) og 4 kræver 1. For 5 prøver man 1 (4 kræver 1, altså 2 mønter), 3 (2 kræver 2, altså 3 mønter) og 4 (1 kræver 1, altså 2 mønter): det bedste er 2. For 6 prøver man 1 (5 kræver 2, altså 3), 3 (3 kræver 1, altså 2) og 4 (2 kræver 2, altså 3): det bedste er 2, med 3 + 3. Grådig ville have betalt 4 + 1 + 1.
At tælle måderne
For at tælle kombinationer tilføjer man mønterne én ad gangen. Med kun den første mønt kan hvert beløb laves på én måde eller slet ikke. Når en ny mønt c kommer med, er måderne at lave et beløb a på de gamle måder, uden c, plus måderne at lave a − c på med c tilladt igen, fordi hver af dem bliver en måde at lave a på ved at lægge en c mere til. Med mønterne 1, 2 og 5 er der 4 måder at lave 5 på: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 og 1 + 1 + 1 + 1 + 1.
Når grådig er nok
Et møntsystem, hvor grådig altid giver færrest mønter, kaldes kanonisk. De fleste moderne valutaer er indrettet sådan, og i 1994 beskrev David Pearson en test, der kontrollerer et møntsystem i et antal trin, som kun vokser polynomielt med antallet af mønter. De gamle britiske mønter var ikke kanoniske: grådig betaler 48 pence som en half crown, en shilling og en sixpence, hvor to floriner ville være nok.
Udforsk det
Åbn appen, skift til visningen Tabel, og tryk på Trin. I tilstanden Færrest mønter er den orange celle det beløb, der regnes på, og den blå celle det mindre beløb, mønten efterlader; rækken nedenunder gemmer den sidste mønt, og til sidst læses mønterne tilbage langs den. Skift til Antal måder, og se antallene vokse række for række, efterhånden som hver mønt kommer med.
Ofte stillede spørgsmål
Er byttepengeproblemet et rygsækproblem?
En nær slægtning. Udgaven med færrest mønter er et ubegrænset rygsækproblem, hvor hver mønt er en genstand, hvis vægt er dens pålydende værdi, rygsækken skal fyldes præcist, og målet er færrest mulige genstande.
Hvad er tidskompleksiteten?
O(k·A) for k slags mønter og et beløb A, i begge udgaver. Tabellen for færrest mønter har A + 1 celler, og tabellen for måderne (k + 1)·(A + 1), selvom én række er nok, hvis cellerne opdateres på stedet.
Hvorfor tælle mønterne i en fast rækkefølge?
Hvis hvert beløb prøvede hver mønt, ville 1 + 2 og 2 + 1 blive talt som to måder. Når mønterne tilføjes én række ad gangen, bygges en kombination altid først af de tidligere mønter, så hver kombination tælles præcis én gang.
Kan mønterne læses tilbage for antal måder?
Ikke som ét enkelt svar, for der er mange. Udgaven med færrest mønter gemmer den sidste mønt for hvert beløb, og det er nok til at genskabe én bedste kombination.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv byttepenge