het veranderingsprobleem richt zich op de kwestie van het vinden van het minimumaantal munten (van bepaalde denominaties) dat samen een bepaald geldbedrag vormt. Het is een speciaal geval van het integer knapzak probleem, en heeft toepassingen breder dan alleen valuta.
het is ook de meest voorkomende variatie van het muntwisselingsprobleem, een algemeen geval van verdeling waarin, gezien de beschikbare denominaties van een oneindige reeks munten, het doel is het aantal mogelijke manieren te achterhalen om een bepaalde hoeveelheid geld te veranderen, zonder rekening te houden met de volgorde van de munten.
verandering aanbrengen is minimalisatie probleem, we kiezen de oplossing waarbij we minimaal aantal munten moeten geven voor een bepaald bedrag.
- hebzuchtige methode
2. Dynamische methode
dynamisch programmeren
een klassieke dynamische programmeerstrategie werkt naar boven door de combinaties van alle kleinere waarden te vinden die zouden optellen tot de huidige drempelwaarde.Dus, bij elke drempel, alle eerdere drempels worden mogelijk beschouwd om omhoog te werken naar het doel bedrag W. Om deze reden, deze dynamische programmering aanpak kan een aantal stappen die ten minste kwadratisch in het doel bedrag W.
optimale munt verandering we hebben gezien dit, u wilt verandering maken met behulp van een systeem van denominaties, met behulp van het kleinste aantal munten mogelijk. Soms geeft het hebzuchtige algoritme de optimale oplossing. Maar soms niet-een voorbeeld was het systeem (12, 5, 1), waar de dynamische algoritme geeft 15 = 12 + 1 + 1 + 1 maar een beter antwoord is 15 = 5 + 5 + 5. maar dynamisch geeft altijd optimale oplossing of mogelijke minimale munten binnen die noemers.
stappen: –
We zullen de minimale no vinden. van de munten die nodig zijn voor het bedrag .
bedrag is het bedrag waarvoor we de wijziging aanbrengen.
We zullen eerst min instellen. geen. van de benodigde munten, d.w.z., min = INFINITY
dit betekent dat we in eerste instantie niet weten hoeveel munten er nodig zijn.
dan controleren we elke denominatie Munten en zien of het kan worden gebruikt om de oplossing te krijgen.
indien mogelijk werken we de min en coin variabelen bij.
waar, min = minimum no. of coins required for making change for amount
coin = first index of the coin in the solution
voorbeeld:
bedrag = 5
munten = {1,2,3}
manieren om verandering aan te brengen = 5
