When can a greedy algorithm solve the coin change problem?

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.

Answer

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(n3) 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(n2) possible values which must contain the smallest counterexample. Each can be tested with O(n) arithmetic operations, giving us an O(n3) 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(n2) algorithm for deciding whether a tight coin system of n coins is canonical.

There is also some discussion in this se.math question.

Attribution
Source : Link , Question Author : The Unfun Cat , Answer Author : Community

Leave a Comment