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 ðŸ˜›

Hey I just stumbled onto this page and it think it is awesome. Keep up the good work!

2 0