Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

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

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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. –  The Unfun Cat Nov 12 '12 at 8:05
    
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. –  Mark Dominus Nov 12 '12 at 13:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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