purist's blog

By purist, history, 6 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

| Write comment?
»
6 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.

»
6 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