29
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Dima Chubarov
    Commented Nov 8, 2012 at 11:04
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dima Chubarov
    Commented Nov 8, 2012 at 11:16
  • $\begingroup$ @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. $\endgroup$
    – The Unfun Cat
    Commented Nov 8, 2012 at 12:27
  • $\begingroup$ I'll upvote the question and if nobody jumps in, summarize MNT with a few examples over the weekend. $\endgroup$
    – Dima Chubarov
    Commented Nov 8, 2012 at 12:31
  • $\begingroup$ See also this related question; in particular, the linked paper by Shallit may be of interest. $\endgroup$
    – Raphael
    Commented Nov 12, 2012 at 11:34

1 Answer 1

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – The Unfun Cat
    Commented Nov 12, 2012 at 8:05
  • $\begingroup$ 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. $\endgroup$
    – Mark Dominus
    Commented Nov 12, 2012 at 13:27
  • $\begingroup$ 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 $\endgroup$
    – The Godfather
    Commented Dec 9, 2018 at 11:57
  • $\begingroup$ @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. $\endgroup$
    – RBarryYoung
    Commented Jan 4, 2020 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.