Maths in a minute: Is greed good?

Vending machines that don't return change are annoying, especially if the prices they demand aren't nice round figures you can make up with a single coin. If that's the case, then there's nothing but to cram through your wallet, fishing out the right coins to make up the amount exactly. What's the best way of doing that? Without noticing many of us probably follow this recipe: find the biggest (as in largest denomination) coin that fits into the amount, then the next-biggest that fits into the remainder, and so on, until you (hopefully) hit the required sum. As an example, if you're being asked for 85p, you probably fish a 50p coin out first, then a 20p coin, then a 10p coin, and finally a 5p coin. And what if you haven't got all of the coins just mentioned in your wallet? In that case you follow the same recipe using what you've got.

This greedy recipe (greedy because you always go for the biggest coin that fits) seems to offer the best solution in that it seems to involve the fewest number of coins to make up the amount you need. For example, supposing you do have a 20p coin, but decide to go for two 10p coins instead, you increase the number of coins to make up 85p from four to five. So the greedy algorithm seems useful, not just for people struggling with vending machines, but also for cashiers returning change to customers.

But is greed really always the best option? It turns out that this depends on the coins that are available. Imagine, for example, you need to make up 8p. Greed would tell you to go for a 5p coin, then a 2p coin and then a 1p coin. And that's indeed the smallest number of coins to make up 8p with if you are using Pound Sterling, Euros, US Dollars, and most other currencies. But now imagine a currency that in addition to these denominations also has a 4p coin. Then you could make up 8p with two of those, beating the greedy strategy by one. Such a currency system might seem silly but it's not unheard-of: the pre-decimal British coinage system was one for which the greedy recipe failed when it came to minimising the number of coins needed to make up a given amount.