förändringsproblemet tar upp frågan om att hitta det minsta antalet mynt (av vissa valörer) som lägger till en viss summa pengar. Det är ett specialfall av heltal ryggsäck problem, och har applikationer bredare än bara valuta.

det är också den vanligaste variationen av myntbytesproblemet, ett allmänt fall av partition där, med tanke på de tillgängliga valörerna för en oändlig uppsättning mynt, är målet att ta reda på antalet möjliga sätt att göra en förändring för en viss summa pengar, utan att ta hänsyn till myntens ordning.

att göra förändring är minimeringsproblem, vi väljer lösningen där vi måste ge minsta antal mynt för givet belopp.

1. girig metod

2. Dynamisk metod

dynamisk programmering

en klassisk dynamisk programmeringsstrategi fungerar uppåt genom att hitta kombinationerna av alla mindre värden som skulle summera till den aktuella tröskeln.Således, vid varje tröskel, anses alla tidigare tröskelvärden potentiellt fungera uppåt till målbeloppet W. av denna anledning kan denna dynamiska programmeringsmetod kräva ett antal steg som är minst kvadratiska i målbeloppet W.

optimal myntbyte vi har sett detta, du vill göra ändringar med hjälp av ett system med valörer, med det minsta antalet mynt som möjligt. Ibland ger den giriga algoritmen den optimala lösningen. Men ibland gör det inte-ett exempel var systemet (12, 5, 1), där den dynamiska algoritmen ger 15 = 12 + 1 + 1 + 1 men ett bättre svar är 15 = 5 + 5 + 5. men dynamic ger alltid optimal lösning eller möjliga minimi mynt inom dessa nämnare.

steg: –

vi hittar minsta Nej. av mynt som krävs för beloppet .
belopp är det belopp som vi gör ändringen.

Vi kommer först att ställa in min. Nej. av mynt som krävs, dvs., min = INFINITY
Detta innebär att vi från början inte vet hur många mynt kommer att behövas.

sedan kontrollerar vi varje valörsmynt och ser om det kan användas för att få lösningen.

om det är möjligt uppdaterar vi min-och myntvariablerna.
var, min = minimum Nej. mynt som krävs för att göra förändring för belopp
mynt = första index av myntet i lösningen

exempel:

belopp = 5

mynt = {1,2,3}

sätt att göra förändring = 5