Algorithme pour trouver des coupures de devises optimales

8

Mark vit dans un petit pays peuplé de gens qui ont tendance à trop penser aux choses. Un jour, le roi du pays décide de repenser la monnaie du pays pour rendre le changement plus efficace. Le roi veut minimiser le nombre de pièces attendu pour payer exactement tout montant jusqu'à (mais sans inclure) le montant de la plus petite facture papier.

Supposons que la plus petite unité monétaire soit la pièce. La plus petite facture papier du royaume vaut pièces. Le roi décide qu'il ne doit pas y avoir plus de différentes dénominations de pièces en circulation. Le problème est donc de trouver un set \ {d_1, d_2, ..., d_m \} d'entiers de \ {1, 2, ..., n - 1 \} qui minimise \ frac {1} {n-1} \ sum_ {i = 1} ^ {n-1} {c_1 (i) + c_2 (i) + ... + c_m (i)} sous réserve de c_1 (i) d_1 + c_2 (i) d_2 + ... c_m (i) d_m = i .nmm{d1,d2,...,dm}{1,2,...,n1}1n1i=1n1c1(i)+c2(i)+...+cm(i)c1(i)d1+c2(i)d2+...cm(i)dm=i

Par exemple, prenez l'USD standard et ses dénominations de pièces de {1,5,10,25,50} . Ici, la plus petite facture papier vaut 100 de la plus petite pièce. Il faut 4 pièces pour faire 46 cents en utilisant cette monnaie; nous avons c1(46)=1,c2(46)=0,c3(46)=2,c4(46)=1,c5(46)=0 . Cependant, si nous avions des pièces de {1,15,30} , il ne faudrait que 3 pièces: c1(46)=1,c2(46)=1,c3(46)=1 . Lequel de ces ensembles de coupures minimise le nombre moyen de pièces pour faire une somme allant jusqu'à 99 cents inclus?

Plus généralement, étant donné n et m , comment pourrait-on déterminer algorithmiquement l'ensemble optimal? De toute évidence, on pourrait énumérer tous les sous-ensembles m viables et calculer le nombre moyen de pièces nécessaires pour faire des sommes de 1 à n1 , en gardant une trace optimale en cours de route. Puisqu'il y a environ C(n-1,m) m (qui ne sont pas tous viables, mais quand même), cela ne serait pas terriblement efficace. Pouvez-vous faire mieux que ça?

Patrick87
la source
Si m <n - 1, alors la solution n'aura-t-elle pas toujours exactement m dénominations? Si j'ai une solution avec k pièces pour (k <m <n - 1), je peux toujours réduire un compte de pièces pour un compte> 0 à 1 en ajoutant une dénomination juste pour cela, réduisant ainsi la moyenne. Si cela est vrai, cela réduit-il le temps d'exécution naïf?
Mike Samuel
@MikeSamuel Sure. Cependant, s'il existe deux solutions également bonnes, l'une avec dénominations et l'autre avec dénominations, cela pourrait être quelque chose que le roi souhaite savoir. Faire plus de types de pièces coûte de l'argent, après tout. mk<m
Patrick87
Je ne pense pas qu'il puisse y avoir deux solutions également bonnes telles que définies uniquement par la somme ci-dessus lorsque m <n-1. S'il y a une pièce valant k où 1 <= k <n, alors cet élément de la sommation est 1, et s'il n'y a pas une pièce valant k, alors cet élément de la sommation est> 1.
Mike Samuel
@MikeSamuel Je pense que c'est probablement vrai, mais là encore, j'aimerais en quelque sorte voir cela dans le cadre d'une réponse, peut-être avec une certaine motivation. Cela devient en fait un peu compliqué, car les ensembles peuvent être (pour la plupart) sans chevauchement.
Patrick87
Voici un autre fait qui rétrécit l'espace de la solution: une pièce valant 1 doit apparaître dans toutes les solutions.
Mike Samuel

Réponses:

6

Ceci est lié au problème bien connu du changement . En fait, si bien étudié, que cette question a été étudiée pour [1] en utilisant la force brute. Depuis 2003, la difficulté de trouver des dénominations optimales semble être un problème ouvert.m7

Si vous consultez les articles citant Shallit, il semble que les dénominations permettant des stratégies de changement gourmandes étaient d'un intérêt particulier. Il est clair que ces dénominations présentent des avantages dans la pratique.


  1. Ce dont ce pays a besoin est une pièce de 18 pièces de Jeffrey Shallit (2003)
Raphael
la source
2

J'ai deviné (à tort, mais supportez-moi) que la série de pièces serait optimale, car les pièces seraient espacées de façon exponentielle, réduisant ainsi la valeur restante autant que possible par pièce ajoutée. Pour votre exemple, ce serait .{bje| b=n1/m,0je<m}{1,3,9,27,81}

C'est un cran meilleur ( ) que les coupures en USD ( ), mais cela ne veut rien dire.390/99420/99

J'ai écrit un script Haskell hack pour obtenir des chiffres par force brute, car je ne sais pas comment aborder cela analytiquement.
Il s'avère que la distribution exponentielle n'est pas toujours la meilleure: il y en a parfois un peu mieux, par exemple pour on obtient pour mais pour . Ma machine lente ne peut pas atteindre , nous devons donc utiliser des nombres plus petits, ici.(m,n)=(4,30)75/29{20,8,3,1}87/29{27,9,3,1}(5,100)

Cependant, j'ai remarqué que l'erreur semble être assez petite. La plupart du temps, la division des sommes donne quelque chose commençant par un 1.0 ..., j'ai donc effectué quelques tests supplémentaires.

À partir d'un ensemble de tests avec et , nous obtenons une erreur moyenne de notre croissance exponentielle par rapport à la meilleure solution de avec un écart-type de .3m56n401.120,085

Vous pourriez faire valoir que les paramètres de test sont plutôt petits, mais comme vous le faites remarquer, c'est juste beaucoup de force brute si vous définissez (il y a très probablement une meilleure solution, mais c'était une excellente excuse pour se relâcher et faire quelques Haskell).n=100


Voici ma suite de tests, si vous voulez l'essayer:

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

J'ai fait le test avec

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