endringsproblemet løser spørsmålet om å finne minimum antall mynter (av visse kirkesamfunn) som legger opp til en gitt sum penger. Det er et spesielt tilfelle av heltall knapsack problem, og har programmer bredere enn bare valuta.Det er også den vanligste varianten av myntendringsproblemet, et generelt tilfelle av partisjon der, gitt de tilgjengelige valørene til et uendelig sett med mynter, er målet å finne ut antall mulige måter å gjøre en endring for en bestemt sum penger uten å vurdere rekkefølgen på myntene.
å gjøre endring er minimeringsproblem, vi velger løsningen der vi må gi minimum antall mynter for gitt beløp.
- Grådig Metode
2. Dynamisk Metode
dynamisk programmering
en klassisk dynamisk programmeringsstrategi fungerer oppover ved å finne kombinasjonene av alle mindre verdier som vil summere til gjeldende terskel.Derfor kan denne dynamiske programmeringsmetoden kreve et antall trinn som er minst kvadratisk I målbeløpet W.
optimal myntendring Vi har sett dette, du vil gjøre endring ved hjelp av et system av kirkesamfunn, ved hjelp av det minste antall mynter som er mulig. Noen ganger gir den grådige algoritmen den optimale løsningen. Men noen ganger gjør det ikke – et eksempel var systemet (12, 5, 1), hvor den dynamiske algoritmen gir 15 = 12 + 1 + 1 + 1 men et bedre svar er 15 = 5 + 5 + 5. men dynamisk gir alltid optimal løsning eller mulige minimumsmynter innenfor denominatorene.
Trinn: –
vi finner minimumsnummeret. av mynter som kreves for beløpet .
Beløpet er beløpet som vi gjør endringen.
vi vil først sette min. ingen. av mynter som kreves dvs., min = INFINITY
Dette betyr at vi i utgangspunktet ikke vet hvor mange mynter som trengs.
så sjekker vi hver pålydende mynter og ser om det kan brukes til å få løsningen.
hvis det er mulig, oppdaterer vi min-og myntvariablene.
hvor, min = minimum nr. mynt = første indeks av mynten i løsningen
Eksempel:
Beløp = 5
mynter = {1,2,3}
Måter å gjøre endring = 5
