When can a greedy algorithm solve the coin change problem?

Question

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.

• Dima Chubarov: For binary knapsack problem there is an easily formulated criterion: greedy algorithm solves the problem if for all denominations $c_i > \Sigma_{j=1}^{i-1} c_j$. Not so easy for coin change (knapsack with arbitrary integral variables). Do you need an exposition of Magazine, Nemhauser and Trotter?
• Dima Chubarov: The statement in the paper by Dexter Kozen says that if the greedy algorithm agrees with the optimal for all $v < c_{n-1} + c_n,ドル then it will give an optimal solution for arbitrary $v$. I see nothing wrong with this statement.
• The Unfun Cat: @Dmitri Chubarov Thanks, now I understand how the bonus q works. Is it akin to strong induction? As to your other question, I'd like an answer that gives a solution and preferably a proof.
• Dima Chubarov: I'll upvote the question and if nobody jumps in, summarize MNT with a few examples over the weekend.
• Raphael: See also this related question; in particular, the linked paper by Shallit may be of interest.

Answer 1

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.

• The Unfun Cat: Thanks. I see the question is much more involved than I thought - I guess that is why you didn't post the actual criteria? My idea that "if all the coins are multiples of each other the greedy algorithm gives an optimal result" was obviously too simple.
• Mark Dominus: I didn't post the actual criteria because I didn't remember offhand and I didn't have time to reread the paper. You should, of course, feel free to edit my answer.
• okainov: I read the answer and the article couple of times, but I was not able to find human-readable criteria of canonical coin system. It would be great if you could add example, i.e. how to test suggested system 1,5,10,20
• RBarryYoung: @TheGodfather Your case is much easier than the general case. Obviously any coin set that is sequenced multiples of the prior coin can be solved optimally with the greedy algorithm. However, there are many less obvious case that can also be solved with the greedy algorithm.