purist's blog

By purist, history, 3 years ago, In English

I observed that some of the coin sets for coin change problem(getting minimum number of change coins for given amount) gives same solution with dp solution and greedy solution. I was wondering what is necessary and sufficient condition for getting optimal solution using greedy approach?

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

A sufficient condition is that the coin denominations are multiple of one another. I don't know any necessary condition though.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

If a greedy algorithm works then the coin system is said to be "canonical". A stricter sufficient (but still not necessary) condition than the one LanceTheDragonTrainer has provided is the following: "In any case where there is no coin whose value, when added to the lowest denomination, is lower than twice that of the denomination immediately less than it, the greedy algorithm works."

This and a more mathematically rigorous answer can be found in this stackoverflow thread: https://stackoverflow.com/questions/13557979/why-does-the-greedy-coin-change-algorithm-not-work-for-some-coin-sets

The following paper, if you have the patience to read it, provides a complete answer for a four coin system and a five coin system, and also provides an algorithm that identifies whether a given coin system is canonical or not. https://arxiv.org/abs/0809.0400

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

A sufficient condition for greedy approach to work in coin change problem is that all the larger denomination are multiples of all other smaller denominations. eg. [1, 2, 4, 8, 32]

Why greedy works in such condition : It assumes that the larger denomination coin is a better choice, since n number of smaller denomination coins is equivalent to the single larger denomination coin. So why fill the bag with extra coins of small denomination when you can achieve the same result by choosing a single coin of larger denomination. This was possible because n is a positive integer. That is the larger denomination is a multiple of the smaller denomination.

Consider this case where greedy fails:

Denomination : [1, 5, 6, 9] (9 & 6 are not a multiple of 5)

Target : 11

Solution as per Greedy Approach : [9, 1, 1]

Optimal Solution : [5, 6]

Why does greedy fails for the above case? Because Greedy assumed that choosing 9 would be better, thinking every smaller denomination if chosen would result into more number coins as compared to choosing a single coin 9. And once it fixes 9. The only option to cover up the remaining value is to choose two coins of 1.

So basically in second case, since 9 & 6 are not a multiple of 5, hence any number of 5 coins can never be equivalent to 9 or 6. Hence choosing coin 5 creates a separate path than choosing coin 9. Cuz stacking multiple 5 coins can yield a value that can't be achieved by stacking any number of 9 coins.