It’s something that every cashier worth their salt knows how to do with their eyes closed. Your favorite candy bar costs 64¢ but got no change in your pocket? Soon 3 coins: a quarter, dime, and penny totaling 36¢ will be happily jingling in your pocket as you leave the supermarket. But what if we had a 36¢ coin? Then the cashier would hand you a single coin, your receipt, and you’d be enjoying your Kit-Kat in no time. Or even better, a 64¢ coin? You’d be in and out before you could say “Give me a break.”
What repercussions would there be with such a coin system? Say we replaced the quarter with a 36¢ piece. Making change for amounts up to 24¢ would be exactly the same as our standard system, but any amounts higher would be a bit different since we have no quarter. All amounts between 25¢ and 35¢ inclusively would begin with 2 dimes and a nickel to make up for the lack of a quarter. This means 2 more coins are necessary to make change for all these amounts. Making 36¢ in change would only take a single coin whereas in the standard system it takes 3.
Assuming all amounts of change to be made are equally likely, replacing the quarter with a 36¢ piece would actually lower the average number of coins required to make change! With our current system, the average number of coins needed is 4.7, with a low of 1 coin to a high of 9 (for 94¢ and 99¢). If we replaced the quarter with a 36¢ piece, this average actually decreases to 4.4 with a high of only 7 (note that 94¢ only requires 6 coins and 99¢ requires 7).
But what if we continued down this path of trying to limit the average number of coins needed to make change? Which coin or coins should we change, or even add or remove?
There exists another class of coin systems that makes greedy algorithms not return the optimal solution. These are systems where 2 of one coin is worth more than 1 of the next highest valued coin. For example, if we replaced the dime with a 14¢ piece and you wanted to make 28¢ in change. Using the normal greedy algorithm we would choose 1 quarter and 3 pennies for a total of 4 coins. But two 14¢ pieces would be twice as efficient only requiring 2 coins! This is all fine and good but how would be go about figuring out the optimal way of making change for each amount? This is where a dynamic algorithm comes into play.
Let’s continue working with this system where we’ve replaced the dime with a 14¢ piece. Let’s investigate how we’d go about making change. It should be fairly obvious that every coin system requires a penny.
- Making 1¢ in change is simple: a single penny!
- To make 2¢ in change, let’s first put down a single coin of each value less than 2¢. Well, the only coin matching that criteria is the penny. Ok, so we have 1¢ down but we still have 1¢ left to make. But we already know how to make 1¢ in change from the previous step: 1 penny! So, to make 2¢ in change we need 2 pennies
You might be saying, “Uhh, who in their right mind would think that much into making 2¢ in change?!” It will become apparent when we look at the case of 28¢.
Assume we’ve already computed the optimal way to make change for all amounts up to 27¢. Let’s use the same method as above to figure out how to make change for 28¢.
- Put down a single coin of each value less than 28¢: 1¢, 5¢, 14¢, and 25¢. Respectively, that leaves us with 27¢, 23¢, 14¢, and 3¢ left to make.
- But we already know how to make change for each of these amounts. We already used the exact same process to know that making 27¢ requires 3 coins, 23¢ requires 6 coins, 14¢ requires only 1, and 3¢ requires 3 coins.
- Choosing the smallest of the options leaves us with two 14¢ pieces equaling 28¢ and we’re done.
Continuing this process gives an average of only 4.04 coins!
But what is the best set of 5 coins we could choose to limit the average number coins returned in our change? What if we replaced all the standard coins? It’s questions like these that are why we invented the personal computer. A quick computer program gives the solution:
A penny, a nickel, an 18¢ piece, and a quarter.
Yup, all we’d have to do is replace the dime with an 18¢ piece and we would decrease the average number of coins returned in our change from 4.4 to 3.89 with a maximum of only 6 coins to make 99¢ (and some others)!
Could we ever adopt this coin system? Probably not, for 2 main reasons:
- Historical reasons. We’ve been using the current system forever.
- Greedy algorithm doesn’t work. Cashiers would have to memorize how to make change for each amount.
A.N.G.N. 