3

To make $6.39, you can choose:

  • $5 bill
  • $1 bill to make $6.
  • 25¢ coin, to make $6.25
  • 10¢ coin, to make $6.35
  • Four 1¢ coins, to make $6.39.

However it doesn't work if the currency has coins with weights of 1,7, and 10. My question is, why does the greedy algorithm work [efficiently] only for a few weights? What are the conditions to be satisfied for the given set of weights to satisfy the greedy algorithm and be optimal at the same time?

BJ Myers
  • 6,617
  • 6
  • 34
  • 50
sarath
  • 57
  • 7
  • What you mean by "efficient"/"optimal" ? Fewest number of operations ? Fewest number of coins in result ? Something else ? – Paul R Jul 08 '13 at 08:07
  • @PaulR Minimizing the number of coins needed. Do you think I should edit the question details to make it more clear? – sarath Jul 08 '13 at 08:13
  • 1
    [For those of us **not** extensively familiar with US currency](http://en.wikipedia.org/wiki/US_currency). It might be helpful to summarise this in the question. – Bernhard Barker Jul 08 '13 at 09:01
  • possible duplicate of [Why does the greedy coin change algorithm not work for some coin sets?](http://stackoverflow.com/questions/13557979/why-does-the-greedy-coin-change-algorithm-not-work-for-some-coin-sets) – j_random_hacker Jul 08 '13 at 18:23

2 Answers2

2

This exact problem is examined in 'A polynomial-time algorithm for the change-making problem' by David Pearson.

Unfortunately, it doesn't provide an elegant mathematical property that answers the question. It is based on the fact that if the greedy algorithm doesn't work, a counterexample will be among a finite number of values and these values have properties which make it cheap to check each one.

svinja
  • 5,495
  • 5
  • 25
  • 43
0

Some answers can be found in this article: http://arxiv.org/pdf/0801.0120v2.pdf

(At least according to their abstract, I didn't read the whole paper)

Vincent
  • 677
  • 2
  • 7
  • 19