How will greedy work in this coin change case [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

The problem is here

Say I have just 25-cent, 10-cent and 4-cent coins and my total amount is 41. Using greedy, I'll pick 25-cent and then 10-cent, and then the remaining 6 cents can not be made.

So my question is, does greedy in this case will tell me that there is no solution?

Answer 1

It looks like your problem was answered right in the the Greedy algorithm wiki: http://en.wikipedia.org/wiki/Greedy_algorithm#Cases_of_failure

Imagine the coin example with only 25-cent, 10-cent, and 4-cent coins. The greedy algorithm would not be able to make change for 41 cents, since after committing to use one 25-cent coin and one 10-cent coin it would be impossible to use 4-cent coins for the balance of 6 cents, whereas a person or a more sophisticated algorithm could make change for 41 cents with one 25-cent coin and four 4-cent coins.

Answer 2

The greedy algorithm mentioned in your link assumes the existence of a unit coin. Otherwise there are some integer amounts it can't handle at all.

Regarding optimality - as stated there, it depends on the available coins. For {10,5,1} for example the greedy algorithm is always optimal (i.e. returns the minimum number of coins to use). For {1,3,4} the greedy algorithm is not guaranteed to be optimal (it returns 6=4+1+1 instead of 6=3+3).

Answer 3

It seems that greedy algorithm is not always the best and this case is used as example to illustrate when it doesn't work

See example in Wikipedia