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.

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


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
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.

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

Leave a Comment