How to tell if greedy algorithm suffices for finding minimum coin change?

Question

The minimum coin change problem is an NP-complete problem but for certain sets of coins the greedy algorithm (choose largest denominations first) works. Given a set of integers denoting coin-values, what's the fastest algorithm to determine if the greedy algorithm suffices or not? One obvious way is to build up your dynamic programming solution till the largest denomination and see for each if it yields a better solution than the greedy way. But is there a faster "math-way" of detecting it?

Answer 1

I recently came up with 1 solution that seemed to show if the given 2 conditions are satisfied, the greedy algorithm would yield the optimal solution.

a) The G.C.D (All the denominations except 1) = 2nd Smallest denomination.

b) The sum of any 2 consecutive denominations must be lesser than the 3rd consecutive denomination.

For eg. c2 + c3 < c4.

(Where c1 = 1; c2, c3, c4 are coin denominations in ascending order).

I understand this is not a complete solution. However, I believe that if these 2 conditions are met, the greedy algorithm will yield the optimal solution.

Answer 2

The paper by Pearson A polynomial-time algorithm for the change-making problem Operation Research Letters 33:3 (May 2005), pp. 231-234 gives a polynomial time algorithm to find the minimal counterexample to the greedy algorithm (if it exists). No exhaustive search required, his main theorem narrows down the set of candidates a lot.