Endringsskapende problem - Change-making problem
De endringsprosesser problem adresser 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 heltalssekken , og har applikasjoner bredere enn bare valuta.
Det er også den vanligste varianten av myntbytteproblemet , et generelt partisjonstilfelle 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 mengde penger, uten å ta hensyn til rekkefølgen på myntene.
Det er svakt NP-hardt , men kan løses optimalt i pseudopolynomisk tid ved dynamisk programmering .
Matematisk definisjon
Myntverdier kan modelleres etter et sett med n distinkte positive heltallverdier (hele tall), ordnet i økende rekkefølge som w 1 til w n . Problemet er: gitt en mengde W , også et positivt heltall, for å finne et sett med ikke-negative (positive eller null) heltall { x 1 , x 2 , ..., x n }, hvor hvert x j representerer hvor ofte mynten med verdi w j brukes, noe som minimerer det totale antallet mynter f ( W )
underlagt
Eksempler uten valuta
En anvendelse av endringsskapende problem kan bli funnet i å beregne måtene man kan lage en ni dart finish i et spill med dart.
En annen applikasjon er å beregne den mulige atomiske (eller isotopiske) sammensetningen av en gitt masse/ladningstopp i massespektrometri.
Metoder for å løse
Enkel dynamisk programmering
En klassisk dynamisk programmeringsstrategi fungerer oppover ved å finne kombinasjonene av alle mindre verdier som vil utgjøre den nåværende terskelen. Således, ved hver terskel, alle tidligere terskler er potensielt vurdert å arbeide oppover for å målbeløpet W . Av denne grunn krever denne dynamiske programmeringsmetoden en rekke trinn som er O ( nW), hvor n er antall mynttyper.
Gjennomføring
Følgende er en dynamisk programmeringsimplementering (med Python 3) som bruker en matrise for å holde oversikt over de optimale løsningene på delproblemer, og returnerer minimum antall mynter, eller "Infinity" hvis det ikke er noen måte å gjøre endringer med mynter gitt. En annen matrise kan brukes for å skaffe myntsett for den optimale løsningen.
def _get_change_making_matrix(set_of_coins, r: int):
m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)]
for i in range(1, r + 1):
m[0][i] = float('inf') # By default there is no way of making change
return m
def change_making(coins, n: int):
"""This function assumes that all coins are available infinitely.
n is the number to obtain with the fewest coins.
coins is a list or tuple with the available denominations.
"""
m = _get_change_making_matrix(coins, n)
for c in range(1, len(coins) + 1):
for r in range(1, n + 1):
# Just use the coin coins[c - 1].
if coins[c - 1] == r:
m[c][r] = 1
# coins[c - 1] cannot be included.
# Use the previous solution for making r,
# excluding coins[c - 1].
elif coins[c - 1] > r:
m[c][r] = m[c - 1][r]
# coins[c - 1] can be used.
# Decide which one of the following solutions is the best:
# 1. Using the previous solution for making r (without using coins[c - 1]).
# 2. Using the previous solution for making r - coins[c - 1] (without
# using coins[c - 1]) plus this 1 extra coin.
else:
m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]])
return m[-1][-1]
Dynamisk programmering med sannsynlighetskonvolusjonstreet
Det sannsynlige konvolusjonstreet kan også brukes som en mer effektiv dynamisk programmeringsmetode. Det sannsynlige konvolusjonstreet slår sammen par mynter for å produsere alle mengder som kan opprettes av det myntparet (med ingen mynt tilstede, bare den første mynten til stede, bare den andre mynten til stede, og begge myntene tilstede), og deretter slå sammen par av disse fusjonerte resultatene på samme måte. Denne prosessen gjentas til de to siste samlingene av utfall er slått sammen til en, noe som fører til et balansert binært tre med W log (W) slike fletteoperasjoner. Videre, ved å diskretisere myntverdiene, kan hver av disse fletteoperasjonene utføres via konvolusjon, som ofte kan utføres mer effektivt med den raske Fourier -transformasjonen (FFT). På denne måten kan det sannsynlige konvolusjonstreet brukes til å oppnå en løsning i sub-kvadratisk antall trinn: hver konvolusjon kan utføres i n log (n) , og de første (flere) fletteoperasjonene bruker et mindre n , mens den senere (mindre tallrike) operasjoner krever n i størrelsesorden W .
Den probabilistiske konvolusjonstrebaserte dynamiske programmeringsmetoden løser også effektivt den sannsynlige generaliseringen av problemet med endring, der usikkerhet eller uklarhet i målbeløpet W gjør det til en diskret fordeling i stedet for en fast mengde, hvor verdien av hver mynt er likeledes tillatt å være uklar (for eksempel når en valutakurs vurderes), og hvor forskjellige mynter kan brukes med bestemte frekvenser.
Grådig metode
For de såkalte kanoniske myntsystemene, som de som brukes i USA og mange andre land, vil en grådig algoritme for å plukke den største myntenheten som ikke er større enn det gjenværende beløpet som skal gjøres, gi det optimale resultatet. Dette er imidlertid ikke tilfellet for vilkårlige myntsystemer. For eksempel, hvis myntverdiene var 1, 3 og 4, for å lage 6, ville den grådige algoritmen velge tre mynter (4,1,1), mens den optimale løsningen er to mynter (3,3). Det er mulig å teste om et myntsystem er kanonisk (det vil si om den grådige algoritmen alltid løser sitt endringsproblem optimalt) i polynomtid .
Relaterte problemer
Det "optimale valørproblemet " er et problem for folk som designer helt nye valutaer. Den spør hvilke valører som skal velges for myntene for å minimere gjennomsnittskostnaden for å gjøre endringer, det vil si gjennomsnittlig antall mynter som trengs for å gjøre endringer. Versjonen av dette problemet antok at de som foretar endringer vil bruke minimum antall mynter (fra de pålydende kirkesamfunnene). En variant av dette problemet antar at menneskene som gjør endringer vil bruke den "grådige algoritmen" for å gjøre endringer, selv når det krever mer enn minimum antall mynter. De fleste nåværende valutaer bruker en 1-2-5-serie , men noen andre sett med valører vil kreve færre mynter eller et mindre gjennomsnittlig antall mynter for å gjøre endringer eller begge deler.