Making change

(no votes yet)

Loading...

Consider the following hypothetical situation:

You are a cashier and you have to give the customer $0.40 in change, however, you have no nickels left in your till. The goal is to minimize the number of coins that the customer receives. How do you do it?

Well this actually happened, and the process the cashier went through was to:

• first take out a quarter (the highest denomination coin below $0.40),
• then take out a dime (the next highest denomination below $0.15),
• then finally, take out 5 pennies (since there is no nickels).

This produces 7 coins! The cashier realized this was not good, thought for a moment, then grabbed 4 dimes, which is the optimal solution in this case.

The “Change-making problem” is a well known problem you may have encountered if you have studied optimization. The problem is to see how one can give change with the least number of coins of given denominations.

The interesting thing is that for currency in North America, the greedy algorithm always produces an optimal solution (i.e. picking the largest denomination of coin which is not greater than the remaining amount). As we saw in the above example, if nickels were not allowable coins, the greedy algorithm would no longer produce an optimal solution for our currency denominations.

Check out the wikipedia links above for more info about this problem 😛