Algorithm to find optimal currency denominations

Question

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?

Answer 1

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)

Answer 2

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] ]

Answer 3

I found out that for m=2 the set should be {1, floor(√n)+1} or {1, ceil(√n)} unless n is a perfect square times the unit the two numbers are equal, if n is a perfect square,both √n and √n+1 work the best

Answer 4

I think that the optimal solution is when a denomination is used it should be used at most (m√)n times and also using as close denominations as the value as possible. I tried using {1,3,7,16,40} for n= 100 (or 99) as I tried to generalise the m=2 solution, however 28 is better made as 7+7+7+7 rather than 16+7+3+1+1 and similarly 68 as 40+4×7 rather than 40+16+7+1+1 so it skips using 16 which is closer to 28 than 7 is. Also 21= 7+7+7=16+3+1+1 , 37= 16+7+7+7=16+16+3+1+1, 61= 40+7+7+7=40+16+3+1+1, 77=40+16+7+7+7=40+16+16+3+1+1 Yes I found many. What is interesting about this set is that you can replace 3+3+1 with 7, 7+7+1+1 with 16, 16+16+7+1 with 40, and weirdly 16+3+1+1 with 7+7+7