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?

• Mike Samuel: 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?
• Patrick87: @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.
• Mike Samuel: 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.
• Patrick87: @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.
• Mike Samuel: Here's another fact that narrows the solution space: a coin worth 1 has to appear in all solutions.

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

• Community: As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.

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 ×ばつ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

• Community: As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.

Answer 5

I did a brute force method in excel for a five coin dollar basis, creating a layout of all outcomes under 20 coins from a given set of coin denominations. For instance, given denominations of 1, 5, 10, 25, 50, I set up a brute force calculation that looked at all possible coin piles under a dollar, inspecting each pile to see if it is a minimal coin count for its currency value. I end up with 99 minimal piles and total up the coins, producing 420 coins. I did not include a pile for the dollar since it can be replaced by a dollar bill.

I wrote a macro that explores the solution space for the model. The set of coins that produce the minimal total coins in the 99 piles is: 1, 5, 16, 23, 33. The count of the coins in the 99 minimal piles is 329. I found eight solutions that produce a count of 331. 1, 3, 11, 27, 34 or 1, 4, 9, 24, 35 for example.

• greybeard: (This answer post presents results where the question asks how, algorithmically?)