Myntväxlingsproblemet
En kassör som ger växel tar det största myntet som får plats, sedan nästa, och för euro eller dollar ger det alltid minst antal mynt. Men byt mynten till 1, 3 och 4, så betalar samma vana 6 med tre mynt när två hade räckt. Dynamisk programmering hittar det verkliga minimumet för alla mynt.
Två frågor
Myntväxlingsproblemet finns i två varianter. Den första frågar efter minst antal mynt som ger ett exakt belopp; den kallas också växlingsproblemet. Den andra frågar hur många olika kombinationer av mynt som ger beloppet. I båda får varje myntsort användas hur många gånger som helst, och båda löses genom att bygga svaret för varje belopp av svaren för mindre belopp.
Minst antal mynt, steg för steg
Gör en rad celler för beloppen från 0 upp till målet. Beloppet 0 kräver 0 mynt; alla andra belopp börjar på oändligheten. Gå igenom beloppen i ordning och prova för vart och ett varje mynt c som får plats: cellen för beloppet minus c, plus ett mynt, är en kandidat. Behåll den minsta. Varje cell beror bara på celler till vänster om den, som redan är klara, så en genomgång fyller raden.
Ett exempel
Med mynten 1, 3 och 4: beloppet 1 kräver 1 mynt, 2 kräver 2, 3 kräver 1 (en enda trea) och 4 kräver 1. För 5 provar man 1 (4 kräver 1, alltså 2 mynt), 3 (2 kräver 2, alltså 3 mynt) och 4 (1 kräver 1, alltså 2 mynt): bäst är 2. För 6 provar man 1 (5 kräver 2, alltså 3), 3 (3 kräver 1, alltså 2) och 4 (2 kräver 2, alltså 3): bäst är 2, med 3 + 3. Girig hade betalat 4 + 1 + 1.
Att räkna sätten
För att räkna kombinationer lägger man till mynten ett i taget. Med bara det första myntet kan varje belopp fås ihop på ett sätt eller inte alls. När ett nytt mynt c tillkommer är sätten att få ihop ett belopp a de gamla sätten, utan c, plus sätten att få ihop a − c med c tillåtet igen, eftersom vart och ett av dem blir ett sätt att få ihop a genom att lägga till ett c till. Med mynten 1, 2 och 5 finns det 4 sätt att få ihop 5: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 och 1 + 1 + 1 + 1 + 1.
När girig räcker
Ett myntsystem där girig alltid ger minst antal mynt kallas kanoniskt. De flesta moderna valutor är utformade så, och 1994 beskrev David Pearson ett test som kontrollerar ett myntsystem i ett antal steg som bara växer polynomiellt med antalet mynt. De gamla brittiska mynten var inte kanoniska: girig betalar 48 pence som en halvkrona, en shilling och en sixpence, när två floriner hade räckt.
Utforska
Öppna appen, byt till vyn Tabell och tryck på Steg. I läget Minst antal mynt är den orange cellen beloppet som räknas ut och den blå cellen det mindre belopp som myntet lämnar; raden under sparar det sista myntet, och i slutet läses mynten tillbaka längs den. Byt till Antal sätt och se antalen växa rad för rad när varje mynt tillkommer.
Ofta ställda frågor
Är myntväxlingsproblemet ett kappsäcksproblem?
En nära släkting. Varianten med minst antal mynt är ett obegränsat kappsäcksproblem där varje mynt är ett föremål vars vikt är dess nominella värde, säcken måste fyllas exakt och målet är så få föremål som möjligt.
Vad är tidskomplexiteten?
O(k·A) för k myntsorter och ett belopp A, i båda varianterna. Tabellen för minst antal mynt har A + 1 celler och tabellen för sätten (k + 1)·(A + 1), men det räcker med en rad om cellerna uppdateras på plats.
Varför räkna mynten i en fast ordning?
Om varje belopp provade varje mynt skulle 1 + 2 och 2 + 1 räknas som två sätt. När mynten läggs till en rad i taget byggs en kombination alltid av de tidigare mynten först, så varje kombination räknas exakt en gång.
Kan mynten läsas tillbaka för antal sätt?
Inte som ett enda svar, eftersom det finns många. Varianten med minst antal mynt sparar det sista myntet för varje belopp, och det räcker för att återskapa en bästa kombination.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Prova myntväxling