This is from Discrete Mathematics and its Applications.

Here is the book's section on the greedy alorithm for counting change enter image description here

Here is the problem I am working on, 54(uses 52) enter image description here

Here is what I got for 54

54a. d1 = 3 d2 = 1 d4 = 2
54b. d1 = 1 d2 = 2 d4 = 4
54c. d1 = 3 d2 = 2 d4 = 4
54d. d1 = 1 d2 = 0 d4 = 8

Where d1 - number of quarters, d2 - number of dimes, d4 - number of pennies. Can someone confirm my suspicions that for all of these amounts, the greedy algorithm will use the fewest coins possible because the number of pennies never gets to the amount that a nickel could replace, 5?

  • $\begingroup$ Recheck your answers for (c) and (d), looks like you slipped across to Q53 amounts $\endgroup$ – Joffan Feb 3 '15 at 23:38
  • $\begingroup$ So so it won't use the fewest coins possible for only the last one. Thanks $\endgroup$ – committedandroider Feb 3 '15 at 23:42

The greedy algorithm isn't always optimal, but it depends on the size of the coins used. For example, consider using coins of size 10, 9, and 1. If you use the greedly algorithm to measure 18, you use 8 1s and 1 10, instead of an optimal 2 9s.

On the other hand, if each coin value is an integer multiple if the next smallest coin value, the greedy algorithm will be optimal. This is not quite the situation we are in, because dimes and quarters differ by a factor of 2.5, but my intuition says this will still not be enough to mess up the optimality of the greedy algorithm.

However, if you get rid of nickels, this changes, because 30 cents is 3 dimes but a quarter and five pennies. Without nickels, no optimal solution to a coin problem will use more than four dimes (why?), But with nickels, an optimal solution won't use more than two dimes. Is this fact enough to show the greedy algorithm is optimal with usual coin amounts?


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.