Algoritmo para encontrar denominaciones de moneda óptimas

Mark vive en un pequeño país poblado por personas que tienden a pensar demasiado. Un día, el rey del país decide rediseñar la moneda del país para que el cambio sea más eficiente. El rey quiere minimizar la cantidad esperada de monedas necesarias para pagar exactamente cualquier cantidad hasta (pero sin incluir) la cantidad de la factura en papel más pequeña.

Supongamos que la unidad monetaria más pequeña es la moneda. El billete de papel más pequeño del reino vale monedas. El rey decide que no debe haber más de denominaciones de monedas diferentes en circulación. El problema, entonces, es encontrar un -set de los enteros de que minimiza sujeto a .$n$$m$$m$$\{d_1, d_2, ..., d_m\}$$\{1, 2, ..., n - 1\}$$\frac{1}{n-1}\sum_{i = 1}^{n-1}{c_1(i) + c_2(i) + ... + c_m(i)}$$c_1(i)d_1 + c_2(i)d_2 + ... c_m(i)d_m = i$

Por ejemplo, tome el USD estándar y sus denominaciones de monedas de . Aquí, el billete de papel más pequeño vale 100 de la moneda más pequeña. Se necesitan 4 monedas para hacer 46 centavos usando esta moneda; tenemos . Sin embargo, si tuviéramos denominaciones de monedas de , solo se necesitarían 3 monedas: . ¿Cuál de estos conjuntos de denominaciones minimiza el número promedio de monedas para hacer una suma de hasta 99 centavos?$\{1, 5, 10, 25, 50\}$$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$

De manera más general, dados y , ¿cómo se podría determinar algorítmicamente el conjunto óptimo? Claramente, uno podría enumerar todos los subconjuntos viables y calcular el número promedio de monedas que se necesitan para hacer sumas de 1 a , haciendo un seguimiento del óptimo en el camino. Como hay alrededor de subconjuntos (no todos son viables, pero aún así), esto no sería terriblemente eficiente. ¿Puedes hacerlo mejor que eso?$n$$m$$m$$n - 1$$C(n - 1, m)$ $m$

Esto está relacionado con el conocido problema de hacer cambios . Tan bien estudiado, de hecho, que esta pregunta ha sido investigada para [1] utilizando la fuerza bruta. A partir de 2003, la dureza de encontrar denominaciones óptimas parece ser un problema abierto.$m \leq 7$

Si revisa los artículos que citan a Shallit, parece que las denominaciones que permiten estrategias de cambio ambicioso fueron de particular interés. Está claro que tales denominaciones tienen ventajas en la práctica.

1. Lo que este país necesita es una pieza de 18 c por Jeffrey Shallit (2003)

Supuse (erróneamente, pero tengan paciencia conmigo) que la serie $\{b^i |\ b = \lceil n^{1/m} \rceil, 0 \leq i < m\}$de monedas sería lo óptimo, ya que las monedas estarían espaciadas exponencialmente, reduciendo así el valor restante tanto como sea posible por moneda agregada. Para su ejemplo, esto sería$\{1,3,9,27,81\}$.

Esta es una muesca mejor ($390/99$) que las denominaciones en USD ($420/99$), pero eso no tiene que significar nada.

Escribí una secuencia de comandos de Haskell para obtener algunos números por fuerza bruta, ya que no estoy seguro de cómo abordar esto analíticamente.
Resulta que la distribución exponencial no siempre es la mejor: a veces hay algunas ligeramente mejores, por ejemplo, para$(m,n) = (4,30)$ obtenemos $75/29$ para $\{20,8,3,1\}$ pero $87/29$ para $\{27,9,3,1\}$. Mi máquina lenta no puede llegar a$(5,100)$, así que tenemos que usar números más pequeños, aquí.

Sin embargo, noté que el error parece ser bastante pequeño. La mayoría de las veces, la división de las sumas produce algo que comienza con un 1.0 ..., así que realicé algunas pruebas más.

De un conjunto de prueba con $3 \leq m \leq 5$ y $6 \leq n \leq 40$, obtenemos un error promedio de nuestro crecimiento exponencial en comparación con la mejor solución de $1.12$ con una desviación estándar de $0.085$.

Podría argumentar que los parámetros de prueba son bastante pequeños, pero como señala, es solo una fuerza bruta si establece $n = 100$ (lo más probable es que haya una mejor solución, pero esta fue una excelente excusa para aflojar y hacer algo de Haskell).

Aquí está mi paquete de prueba, si quieres probarlo:

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

Hice la prueba con

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