When can a greedy algorithm solve the coin change problem?

ignougroup
Question Detail: Given a set of coins with different denominations $c1, … , cn$ and a value v you want to find the least number of coins needed to represent the value v. E.g. for the coinset 1,5,10,20 this gives 2 coins for the sum 6 and 6 coins for the sum 19. My main question is: when can a greedy strategy be used to solve this problem? Bonus points: Is this statement plain incorrect? (From: How to tell if greedy algorithm suffices for the minimum coin change problem?)

However, this paper has a proof that if the greedy algorithm works for the first largest denom + second largest denom values, then it works for them all, and it suggests just using the greedy algorithm vs the optimal DP algorithm to check it. http://www.cs.cornell.edu/~kozen/papers/change.pdf

Ps. note that the answers in that thread are incredibly crummy- that is why I asked the question anew.

Asked By : The Unfun Cat
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6552

Answered By : Mark Dominus

A coin system is canonical if the number of coins given in change by the greedy algorithm is optimal for all amounts. The paper D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005 offers an $O(n^3)$ algorithm for deciding whether a coin system is canonical, where $n$ is the number of different kinds of coins. From the abstract:

We then derive a set of $O(n^2)$ possible values which must contain the smallest counterexample. Each can be tested with $O(n)$ arithmetic operations, giving us an $O(n^3)$ algorithm.

The paper is quite short. For a non-canonical coin system, there is an amount $c$ for which the greedy algorithm produces a suboptimal number of coins; $c$ is called a counterexample. A coin system is tight if its smallest counterexample is larger than the largest single coin. The paper Canonical Coin Systems for Change-Making Problems provides necessary and sufficient conditions for coin systems of up to five coins to be canonical, and an $O(n^2)$ algorithm for deciding whether a tight coin system of $n$ coins is canonical. There is also some discussion in this se.math question.