# 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?