1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

Since the each coin divides the face value of every larger coin, a single larger coin will always represent an integer multiple of smaller coins.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.