Förändringsproblem

Problemet med förändringar tar upp frågan om att hitta det minsta antalet mynt (av vissa valörer) som summerar till en given summa pengar. Det är ett specialfall av heltalsryggsäcksproblemet och har tillämpningar som är bredare än bara valuta.

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

Det är svagt NP-hårt , men kan lösas optimalt i pseudopolynomtid genom dynamisk programmering .

Matematisk definition

Myntvärden kan modelleras av en uppsättning av $n$ distinkta positiva heltalsvärden (hela tal), arrangerade i ökande ordning som $w 1$ till $w n$ . Problemet är: givet ett belopp $W$ , också ett positivt heltal, för att hitta en uppsättning icke-negativa (positiva eller noll) heltal { $x 1, x 2, ..., x n$ }, där varje $x j$ representerar hur ofta myntet med värdet $w j$ används, vilket minimerar det totala antalet mynt $f (W)$

f(W)=\summa _{j=1}^{n}x_{j}

föremål för

\sum _{j=1}^{n}w_{j}x_{j}=W.

Icke-valuta exempel

En tillämpning av förändringsskapande problem kan hittas i att beräkna hur man kan göra en nio-dartavslutning i ett dartspel.

En annan tillämpning är att beräkna den möjliga atomära (eller isotopiska) sammansättningen av en given massa/laddningstopp i masspektrometri.

Metoder för att lösa

Enkel dynamisk programmering

En klassisk dynamisk programmeringsstrategi arbetar 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 arbeta uppåt till målbeloppet W . Av denna anledning kräver denna dynamiska programmeringsmetod ett antal steg som är O( nW), där n är antalet typer av mynt.

Genomförande

Följande är en dynamisk programmeringsimplementering (med Python 3) som använder en matris för att hålla reda på de optimala lösningarna på delproblem, och returnerar det minsta antalet mynt, eller "Infinity" om det inte finns något sätt att göra förändringar med mynt som ges. En andra matris kan användas för att erhålla uppsättningen mynt för den optimala lösningen.

   
      0            
          
        0    
     

   
    



       
         
              
            
               
                  
            
            
            
               
                    
            
            
            
            
            
            
                         
      def  _get_change_making_matrix  (  set_of_coins  ,  r  :  int  ):  m  =  [[  för  _  i  intervallet  (  r  +  1  ) ]  för  _  i  intervallet  (  len  (  set_of_coins  )  +  1  )]  för  i  i  intervallet  (  1  ,  r  +  1  ):  m  [  ][  i  ]  =  float  (  'inf'  )  # Som standard finns det inget sätt att få ändring  att returnera  m  def  change_making  (  coins  ,  n  :  int  ):  """Denna funktion förutsätter att alla mynt är tillgängliga i oändlighet.  n är antal att få med minst mynt.  mynt är en lista eller tuppel med tillgängliga valörer. """  m  =  _get_change_making_matrix  (  mynt  ,  n  )  för  c  ,  mynt  i  uppräkning  (  mynt  ,  1  )  :  för  r  i  intervall  (  1  ,  n )  +  1  ):  # Använd bara myntet  om  mynt  ==  r  :  m  [  c  ][  r  ]  =  1  # mynt inte kan inkluderas.  # Använd föregående lösning för att göra r,  # exklusive mynt  elif  mynt  >  r  :  m  [  c  ][  r  ]  =  m  [  c  -  1  ][  r  ]  # mynt kan användas.  # Bestäm vilken av följande lösningar som är bäst:  # 1. Använd föregående lösning för att göra r (utan att använda mynt).  # 2. Använd den tidigare lösningen för att göra r - mynt (utan att  # använder mynt) plus detta 1 extra mynt.  annat  :  m  [  c  ][  r  ]  =  min  (  m  [  c  -  1  ][  r  ],  1  +  m  [  c  ][  r  -  mynt  ])  returnera  m  [  -  1  ][  -  1  ]

Dynamisk programmering med det probabilistiska faltningsträdet

Det probabilistiska faltningsträdet kan också användas som ett mer effektivt tillvägagångssätt för dynamisk programmering. Det probabilistiska faltningsträdet slår samman myntpar för att producera alla mängder som kan skapas av det myntparet (med inget mynt närvarande, bara det första myntet närvarande, bara det andra myntet närvarande, och båda mynten närvarande), och sedan slås ihop paren av dessa sammanslagna resultat på samma sätt. Denna process upprepas tills de två sista samlingarna av resultat slås samman till en, vilket leder till ett balanserat binärt träd med W log(W) sådana sammanslagningsoperationer. Dessutom, genom att diskretisera myntvärdena, kan var och en av dessa sammanslagningsoperationer utföras via faltning, vilket ofta kan utföras mer effektivt med den snabba Fouriertransformen (FFT). På detta sätt kan det probabilistiska faltningsträdet användas för att uppnå en lösning i subkvadratiskt antal steg: varje faltning kan utföras i n log(n) , och de initiala (fler talrika) sammanslagningsoperationerna använder ett mindre n , medan de senare (mindre många) operationerna kräver n i storleksordningen W .

Den probabilistiska faltningsträdbaserade dynamiska programmeringsmetoden löser också effektivt den probabilistiska generaliseringen av förändringsskapande problemet, där osäkerhet eller luddighet i målmängden W gör det till en diskret fördelning snarare än en fast kvantitet, där värdet av varje mynt likaså är tillåts vara otydlig (till exempel när en växelkurs övervägs) och där olika mynt kan användas med särskilda frekvenser.

Girig metod

För många verkliga myntsystem, som de som används i USA och många andra länder, kommer en girig algoritm att välja den största valören av mynt som inte är större än den återstående mängden som ska göras att ge det optimala resultatet. Detta är dock inte fallet för godtyckliga myntsystem eller ens vissa verkliga system. Om vi till exempel betraktar de gamla (nu indragna) indiska myntvalörerna på 5, 10, 20 och 25 paise, då för att göra 40 paise, skulle den giriga algoritmen välja tre mynt (25, 10, 5) medan den optimala lösningen är två mynt (20, 20). Ett myntsystem kallas "kanoniskt" om den giriga algoritmen alltid löser sitt förändringsproblem optimalt. Det är möjligt att testa om ett myntsystem är kanoniskt i polynomtid .

Relaterade problem

"optimala valörer " är ett problem för människor som designar helt nya valutor. Den frågar vilka valörer som ska väljas för mynten för att minimera den genomsnittliga kostnaden för att göra förändringar, det vill säga det genomsnittliga antalet mynt som behövs för att göra förändringar. Versionen av detta problem antog att de som gör förändring kommer att använda det minsta antalet mynt (från tillgängliga valörer). En variant av detta problem antar att de som gör förändringar kommer att använda den "giriga algoritmen" för att göra förändringar, även när det kräver mer än det minsta antalet mynt. De flesta nuvarande valutor använder en 1-2-5-serie , men någon annan uppsättning valörer skulle kräva färre valörer av mynt eller ett mindre genomsnittligt antal mynt för att ändra eller båda.

Se även

Vidare läsning

M. Adamaszek, A. Niewiarowska (2010). "Kombinatorik av förändringsproblemet". European Journal of Combinatorics . 31 (1): 47–63. arXiv : 0801.0120 . doi : 10.1016/j.ejc.2009.05.002 . S2CID 13527488 .