# Giving change - what denominations guarantees an optimal greedy algorithm?

I was thinking about how giving change is a greedy algorithm for the optimal result, where the optimal result is getting the lowest amount of bills and coins possible. The algorithm I am referring to is where you go from the largest denomination to the smallest, at each point saying "how many of X bills can I give?", subtracting from the total, and moving down to the next bill.

However, this does not guarantee the optimal solution always.

A simple, constructed example is if your denominations are $1$ cent penny, $\$1.50$bill, and$\$2.00$ bill. If you want to give $\$3$change, this algorithm will make you end up getting a$\$2.00$ bill and $100$ pennies instead of $2$ $\$1.50\$ bills.

So, my question is, what properties of denominations makes this greedy algorithm effective?

## 1 Answer

There is a lot of literature on this subject, giving complex criteria for when the greedy solution works. One easy criterion, assuming that your denominations are integers (e.g. in terms of pennies) and 1 is one of your denominations, and when you sort your denominations in increasing order each denomination is at least twice the previous denomination, then the greedy algorithm will give the optimal solution.

• Interesting.. are there any more "natural" examples than mine for which the greedy algorithm doesn't work? Perhaps an actual national currency somewhere? – MCT Jun 24 '15 at 19:16