Posted by: hrummel | December 2, 2008

## Making Change

The problem of making change using the least number of coins is not as easy as it sounds. The greedy algorithm, i.e take away the highest denomination until we can’t anymore then take the denomination below that so on and so forth doesn’t always work when you use the coins in our society, i.e. penny, 5cent, 10cent, quarter, if you allow the change maker to run out of a certain coin. For example, let’s say someone has to make change for 31cents and has 5 quarters 0 nickels 4 dimes, 10 pennies. If we were to use the greedy algorithm and take away a quarter we would be left with 6 cents and would need to use 6 pennies for a total number of coins = 7 coins. However we can see that we if we used 3 dimes and one penny we would only use 4 coins to make the same amount of change. The following describes the rules for making change that I found:

problems only arise between 30 and 55 in change due. Otherwise you should always use the greedy algorithm.

Once you get to 55 in change due, you should only take away a quarter if you have another quarter ready, so you should only take away two quarters between 50 and 55 or none at all. To see this suppose you have 1 quarter no nickels 6 dimes, 10 pennies and 51 cents to make change for. You could take away a quarter, end up at 26 cents which would take 2 dimes and 6 pennies for a total of 9 coins, however we could do the same with change with 5 dimes and a penny for a total of 6 coins. So between 50 and 55 do not use quarters unless you have another quarter handy if you have no nickels, take away dimes first. between 30 and 49, do not use unless you have at least one nickel AND have more than 2 dimes. In this case you will want to take away dimes until you are below 30 cents. Once you are below 30 cents you can use the greedy algorithm.