ændringsproblemet løser spørgsmålet om at finde det mindste antal mønter (af visse valører), der udgør et givet beløb. Det er et specielt tilfælde af heltal rygsækproblemet og har applikationer bredere end bare valuta.
det er også den mest almindelige variation af møntændringsproblemet, et generelt tilfælde af partition, hvor målet i betragtning af de tilgængelige betegnelser for et uendeligt sæt mønter er at finde ud af antallet af mulige måder at foretage en ændring for et bestemt beløb uden at overveje rækkefølgen af mønterne.
ændring er minimeringsproblem, vi vælger løsningen, hvor vi skal give minimum antal mønter for et givet beløb.
- grådig metode
2. Dynamisk metode
dynamisk programmering
en klassisk dynamisk programmeringsstrategi fungerer opad ved at finde kombinationerne af alle mindre værdier, der ville summe til den aktuelle tærskel.Af denne grund kan denne dynamiske programmeringsmetode kræve et antal trin, der er mindst kvadratisk i målbeløbet v.
optimal møntændring vi har set dette, du vil foretage ændringer ved hjælp af et system med valører ved hjælp af det mindste antal mønter, der er muligt. Nogle gange giver den grådige algoritme den optimale løsning. Men nogle gange er det ikke — et eksempel var systemet (12, 5, 1), hvor den dynamiske algoritme giver 15 = 12 + 1 + 1 + 1 men et bedre svar er 15 = 5 + 5 + 5. men dynamisk giver altid optimal løsning eller mulige minimumsmønter inden for disse nævnere.
trin:-
Vi finder minimumsnr. af mønter, der kræves for beløbet .
beløb er det beløb, som vi foretager ændringen for.
Vi sætter først min. ingen. af mønter kræves dvs., min = INFINITY
det betyder, at vi oprindeligt ikke ved, hvor mange mønter der skal bruges.
så kontrollerer vi hver pålydende mønter og ser om det kan bruges til at få løsningen.
Hvis det er muligt, opdaterer vi min-og møntvariablerne.
hvor, min = minimum Nej. mønter = første indeks for mønten i løsningen
eksempel:
beløb = 5
mønter = {1,2,3}
måder at foretage ændring = 5
