Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills:
$$
s = \sum_{i=1}^k n_i d_i\quad\text{with } n_i > 0, d_i > d_{i-1}
$$
We start with the highest denomination $d$ not exceeding $s$ and subtract it. We repeat this process until $s$ is completely represented. As long as all denominations are available, this simple algorithm guarantees the minimum number of coins or bills used. (This is a little sketchy but I guess we are all familiar with it and it's not central to my question.)
My question is: what property of $d_i$ makes this work? I once heard that the value of any coin must be bigger than the sum of all coins of lower denomination for the greedy algorithm to work. This holds for the typical denomination:
$$
1,2,5,10,20,50,100
$$
However, I wasn't able to come up with a counter example or even a proof. Surely this problem has been studied and I would be glad to know more about it. In fact, I'm not even sure about the right tags — feel free to edit them. I assume the algorithm to find the sum with the minimum number of coins becomes tricky when we no longer can assume that all denominations are available.
Best Answer
The greedy solution is not optimal in general, even for the case when the value of any coin is bigger than the sum of all coins of lower denomination. For example, suppose we have coins of denominations 25, 9, 4, and 1. For 37 cents, the greedy solution uses five coins: one 25, one 9, and three 1s. However, the optimal solution is four coins: one 25 and three 4s.
The problem of finding the minimum number of coins given a set of denominations is called the change-making problem. It's a variant of the famous knapsack problem and is known to be difficult in the general case.
An integer-programming formulation for the change-making problem was given in the answer to this math.SE question: On problems of coins totaling to a given amount.
Added: While the Wikipedia article on the change-making problem claims that the greedy algorithm is optimal for U.S. coins, it provides no proof. The article "Canonical Coin Systems for Change-Making Problems" discusses characterizations for when the greedy algorithm is optimal for coin systems of up to five denominations. It also implies that for systems of larger than five denominations determining when the greedy algorithm is optimal is still an open problem.