Greedy algorithm Prove or disprove that the greedy algorithm for making change always uses the fewest coins possible when the denominations available are pennies (1-cent coins), nickels (5-cent coins), and quarters (25-cent coins).
Does anyone know how to solve this?

After giving out the maximal number of quarters, there will be $0-24$ cents remaining.  Then there will be at most 4 nickels to give out.  After giving out nickels greedily, there will be $0-4$ cents remaining, so there will be at most 4 pennies to give out.  Now, can you prove that we cannot rearrange our change to use fewer coins?
