Mark lives in a tiny country populated by people who tend to over-think things. One day, the king of the country decides to redesign the country's currency to make giving change more efficient. The king wants to minimize the expected number of coins it takes to exactly pay any amount up to (but not including) the amount of the smallest paper bill.

Suppose that the smallest unit of currency is the Coin. The smallest paper bill in the kingdom is worth $n$ Coins. The king decides that there should not be more than $m$ different coin denominations in circulation. The problem, then, is to find a $m$-set $\{d_1, d_2, ..., d_m\}$ of integers from $\{1, 2, ..., n - 1\}$ which minimizes $\frac{1}{n-1}\sum_{i = 1}^{n-1}{c_1(i) + c_2(i) + ... + c_m(i)}$ subject to $c_1(i)d_1 + c_2(i)d_2 + ... c_m(i)d_m = i$.

For instance, take the standard USD and its coin denominations of $\{1, 5, 10, 25, 50\}$. Here, the smallest paper bill is worth 100 of the smallest coin. It takes 4 coins to make 46 cents using this currency; we have $c_1(46) = 1, c_2(46) = 0, c_3(46) = 2, c_4(46) = 1, c_5(46) = 0$. However, if we had coin denominations of $\{1, 15, 30\}$, it would take only 3 coins: $c_1(46) = 1, c_2(46) = 1, c_3(46) = 1$. Which of these denomination sets minimizes the average number of coins to make any sum up to and including 99 cents?

More generally, given $n$ and $m$, how might one algorithmically determine the optimal set? Clearly, one might enumerate all viable $m$-subsets and compute the average number of coins it takes to make sums from 1 to $n - 1$, keeping track of the optimal one along the way. Since there are around $C(n - 1, m)$ $m$-subsets (not all of which are viable, but still), this would not be terribly efficient. Can you do better than that?

  • If m < n - 1, then isn't the solution always going to have exactly m denominations? If I have a solution with k coins for (k < m < n - 1) I can always reduce one coin count for a count > 0 to 1 by adding a denomination just for it, thus reducing the average. If that is true, then does that reduce the naive runtime? – Mike Samuel Jul 13 '12 at 18:22
  • @MikeSamuel Sure. However, if there are two equally good solutions, one with $m$ denominations and one with $k < m$ denominations, that might be something the king is interested in knowing. Making more kinds of coins costs money, after all. – Patrick87 Jul 13 '12 at 18:24
  • I don't think there can be two equally good solutions as defined solely by the summation above when m < n-1. If there is a coin worth k where 1 <= k < n, then that element of the summation is 1, and if there is not a coin worth k, then that element of the summation is > 1. – Mike Samuel Jul 13 '12 at 18:28
  • @MikeSamuel I think that's probably true, but then again, I'd sort of like to see that as part of an answer, possibly with some motivation. It actually gets a little complicated, since the sets can be (mostly) non-overlapping. – Patrick87 Jul 13 '12 at 18:32
  • Here's another fact that narrows the solution space: a coin worth 1 has to appear in all solutions. – Mike Samuel Jul 13 '12 at 18:34
up vote 5 down vote accepted

This is related to the well-known change-making problem. So well-studied, in fact, that this question has been investigated for $m \leq 7$ [1] using brute force. As of 2003, the hardness of finding optimal denominations appears to be an open problem.

If you check the articles citing Shallit, it seems as if denominations enabling greedy change-making strategies were of particular interest. It is clear that such denominations have advantages in practice.


  1. What This Country Needs is an 18c Piece by Jeffrey Shallit (2003)

I guessed (wrongly, but bear with me) that the series $\{b^i |\ b = \lceil n^{1/m} \rceil, 0 \leq i < m\}$ of coins would be the optimal, as the coins would be exponentially spaced, thus reducing the remaining value as much as possible per added coin. For your example, this would be $\{1,3,9,27,81\}$.

This is a notch better ($390/99$) than the USD denominations ($420/99$), but that doesn't have to mean anything.

I wrote a hackish Haskell script to get some numbers by brute force, as I'm not sure right now how to approach this analytically.
It turns out, the exponential distribution is not always the best: there are sometimes slightly better ones, for example, for $(m,n) = (4,30)$ we get $75/29$ for $\{20,8,3,1\}$ but $87/29$ for $\{27,9,3,1\}$. My sluggish machine can't get to $(5,100)$, so we have to use smaller numbers, here.

However, I noticed that the error seems to be quite small. Most of the time, the division of the sums yields something starting with an 1.0..., so I ran some more tests.

From a test set with $3 \leq m \leq 5$ and $6 \leq n \leq 40$, we get an average error of our exponential growing compared to the best solution of $1.12$ with a standard deviation of $0.085$.

You might argue that the test parameters are rather small, but as you point out, it's just a lot to brute force if you set $n = 100$ (there's most probably a better solution, but this was an excellent excuse to slack off and do some Haskell).


Here is my test suite, if you want to try it out:

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

I ran the test with

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.