Algorithmus zum Finden optimaler Währungsbezeichnungen

8

Mark lebt in einem winzigen Land, in dem Menschen leben, die dazu neigen, Dinge zu überdenken. Eines Tages beschließt der König des Landes, die Währung des Landes neu zu gestalten, um Veränderungen effizienter zu gestalten. Der König möchte die erwartete Anzahl von Münzen minimieren, die erforderlich sind, um einen beliebigen Betrag bis zum Betrag der kleinsten Papierrechnung genau zu bezahlen (jedoch nicht einzuschließen).

Angenommen, die kleinste Währungseinheit ist die Münze. Die kleinste Papierrechnung im Königreich ist n Münzen wert . Der König beschließt, dass nicht mehr als m verschiedene Münzwerte im Umlauf sein dürfen. Das Problem besteht also darin, eine m Menge {d1,d2,...,dm} von ganzen Zahlen aus {1,2,...,n1} was 1 minimiert1n1i=1n1c1(i)+c2(i)+...+cm(i)vorbehaltlichc1(i)d1+c2(i)d2+...cm(i)dm=i.

Nehmen Sie zum Beispiel den Standard-USD und seine Münzwerte von . Hier ist die kleinste Papierrechnung 100 der kleinsten Münze wert. Mit dieser Währung werden 4 Münzen benötigt, um 46 Cent zu verdienen. wir haben c 1 ( 46 ) = 1 , c 2 ( 46 ) = 0 , c 3 ( 46 ) = 2 , c 4 ( 46 ) = 1 , c 5{1,5,10,25,50} . Wenn wir jedoch Münzwerte von { 1 , 15 , 30 } hätten , würden nur 3 Münzen benötigt: c 1 ( 46 ) = 1 , c 2 ( 46 ) = 1 , c 3 ( 46 ) = 1 . Welcher dieser Nennwertsätze minimiert die durchschnittliche Anzahl von Münzen, um eine Summe von bis zu 99 Cent zu erhalten?c1(46)=1,c2(46)=0,c3(46)=2,c4(46)=1,c5(46)=0{1,15,30}c1(46)=1,c2(46)=1,c3(46)=1

Allgemeiner , wie könnte man bei n und m algorithmisch die optimale Menge bestimmen? Es ist klar, dass man alle realisierbaren m- Teilmengen aufzählen und die durchschnittliche Anzahl von Münzen berechnen kann, die erforderlich sind, um Summen von 1 bis n - 1 zu erzielen , wobei die optimale auf dem Weg verfolgt wird. Da es ungefähr C ( n - 1 , m ) m- Teilmengen gibt (von denen nicht alle lebensfähig sind, aber immer noch), wäre dies nicht besonders effizient. Kannst du es besser machen?nmmn1C(n1,m) m

Patrick87
quelle
Wenn m <n - 1 ist, hat die Lösung dann nicht immer genau m Nennwerte? Wenn ich eine Lösung mit k Münzen für (k <m <n - 1) habe, kann ich immer eine Münzzahl für eine Zählung> 0 auf 1 reduzieren, indem ich nur dafür einen Nennwert hinzufüge und so den Durchschnitt reduziere. Wenn das stimmt, reduziert das dann die naive Laufzeit?
Mike Samuel
@ MikeSamuel Sicher. Wenn es jedoch zwei gleich gute Lösungen gibt, eine mit Stückelungen und eine mit k < m Stückelungen, könnte der König daran interessiert sein, dies zu wissen. Immerhin kostet es Geld, mehr Arten von Münzen herzustellen. mk<m
Patrick87
Ich denke nicht, dass es zwei gleich gute Lösungen geben kann, wie sie allein durch die obige Summierung definiert sind, wenn m <n-1 ist. Wenn es eine Münze im Wert von k gibt, wobei 1 <= k <n ist, dann ist dieses Element der Summe 1, und wenn es keine Münze im Wert von k gibt, dann ist dieses Element der Summe> 1.
Mike Samuel
@ MikeSamuel Ich denke, das ist wahrscheinlich wahr, aber andererseits würde ich das gerne als Teil einer Antwort sehen, möglicherweise mit etwas Motivation. Es wird tatsächlich etwas kompliziert, da die Sätze (meistens) nicht überlappend sein können.
Patrick87
Hier ist eine weitere Tatsache, die den Lösungsraum einschränkt: In allen Lösungen muss eine Münze im Wert von 1 erscheinen.
Mike Samuel

Antworten:

6

Dies hängt mit dem bekannten Problem der Änderung zusammen . In der Tat so gut untersucht, dass diese Frage mit brutaler Gewalt für [1] untersucht wurde. Ab 2003 scheint die Schwierigkeit, optimale Stückelungen zu finden, ein offenes Problem zu sein.m7

Wenn Sie die Artikel überprüfen , in denen Shallit zitiert wird , scheint es, als wären Konfessionen von besonderem Interesse, die gierige Strategien zur Veränderung ermöglichen. Es ist klar, dass solche Bezeichnungen in der Praxis Vorteile haben.


  1. Was dieses Land braucht, ist ein 18c Stück von Jeffrey Shallit (2003)
Raphael
quelle
2

Ich vermutete (zu Unrecht, aber ertrage es mit mir), dass die Serie von Münzen wäre das Optimum, da die Münzen exponentiell beabstandet wären, wodurch der verbleibende Wert pro hinzugefügter Münze so weit wie möglich verringert würde. In Ihrem Beispiel wäre dies { 1 , 3 , 9 , 27 , 81 } .{bich| b=n1/.m,0ich<m}}{1,3,9,27,81}}

Dies ist eine Kerbe besser ( ) als die USD Stückelung ( 420 / 99 ), aber das muss nicht alles bedeuten.390/.99420/.99

Ich habe ein hackiges Haskell-Skript geschrieben, um einige Zahlen mit brutaler Gewalt zu erhalten, da ich mir derzeit nicht sicher bin, wie ich das analytisch angehen soll.
Es stellt sich heraus, die exponentielle Verteilung ist nicht immer die beste: Es gibt manchmal etwas bessere, zum Beispiel für erhalten wir 75 / 29 für { 20 , 8 , 3 , 1 } aber 87 / 29 für { 27 , 9 , 3 , 1 }(m,n)=(4,30)75/.29{20,8,3,1}}87/.29{27,9,3,1}. Meine träge Maschine kann nicht auf , daher müssen wir hier kleinere Zahlen verwenden.(5,100)

Mir ist jedoch aufgefallen, dass der Fehler recht klein zu sein scheint. Meistens ergibt die Aufteilung der Summen etwas, das mit 1,0 ... beginnt, also habe ich noch einige Tests durchgeführt.

Aus einem Testsatz mit und 6 n 40 erhalten wir einen durchschnittlichen Fehler unseres exponentiellen Wachstums im Vergleich zur besten Lösung von 1,12 mit einer Standardabweichung von 0,085 .3m56n401.120.085

Sie könnten argumentieren, dass die Testparameter eher klein sind, aber wie Sie betonen, ist es nur eine Menge Brute Force, wenn Sie (es gibt höchstwahrscheinlich eine bessere Lösung, aber dies war eine ausgezeichnete Ausrede, um nachzulassen und etwas zu tun Haskell).n=100


Hier ist meine Testsuite, wenn Sie sie ausprobieren möchten:

getopt :: [Integer] -> Integer -> [Integer]
getopt _ 0 = []
getopt coins target = choice:(getopt viable $ target - choice)
                          where
                            viable = filter ((>=) target) coins
                            choice = maximum $ viable

getsum :: [Integer] -> Integer -> Int
getsum coins n = sum $ map length $ map (getopt coins) [1..(n-1)]

buildall :: Integer -> Integer -> [[Integer]]
buildall 1 _ = [[1]]
buildall m n = foldl1 (++) $ map (\am -> map (\x -> x:am) [((head am)+1) .. (n-1)]) $ buildall (m-1) n

buildguess :: Integer -> Integer -> [Integer]
buildguess m n = reverse $ map ((^) $ ceiling $ (fromInteger n)**(1.0/(fromInteger m))) [0..(m-1)]

findopt :: Integer -> Integer -> ([Integer],Int)
findopt m n = foldl1 (\(l@(_,lhs)) -> (\(r@(_,rhs)) -> (if (lhs < rhs) then l else r)))
            $ map (\arr -> (arr,getsum arr n)) $ buildall m n

intcast :: (Integral a,Num b) => a -> b
intcast = fromInteger.toInteger

esterror :: Integer -> Integer -> Double
esterror m n = (intcast $ getsum (buildguess m n) n) / (intcast best)
                 where (_,best) = findopt m n

Ich habe den Test mit durchgeführt

map (uncurry esterror) [(m,n) | m <- [3..5], n <- [6..40] ]
Bitmaske
quelle