Algorithmus zum Finden optimaler Währungsbezeichnungen

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 $\{d_1, d_2, ..., d_m\}$ von ganzen Zahlen aus $\{1, 2, ..., n - 1\}$ was 1 minimiert$\frac{1}{n-1}\sum_{i = 1}^{n-1}{c_1(i) + c_2(i) + ... + c_m(i)}$vorbehaltlich$c_1(i)d_1 + c_2(i)d_2 + ... c_m(i)d_m = 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 $\{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?$c_1(46) = 1, c_2(46) = 0, c_3(46) = 2, c_4(46) = 1, c_5(46) = 0$$\{1, 15, 30\}$$c_1(46) = 1, c_2(46) = 1, c_3(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?$n$$m$$m$$n - 1$$C(n - 1, m)$ $m$

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.$m \leq 7$

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)

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 } .$\{b^i |\ b = \lceil n^{1/m} \rceil, 0 \leq i < 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/99$$420/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 .$3 \leq m \leq 5$$6 \leq n \leq 40$$1.12$$0.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] ]