Coin Change: A Greedy Approach

Question

The problem is that n cents change with quarters, pennies, nickels and pennies and using the smallest total number of coins. In the particular case, when the four names are quarters, tithes, nickels and pennies, we have c1 = 25, c2 = 10, c3 = 5 and c4 = 1.

If we have only quarters, tithes and pennies (and not nickels) , the greedy algorithm will make changes for 30 cents using six coins - a quarter and five pennies, while we could use three coins , namely three decades.

Given the set of items, how can we say whether the greedy approach creates the optimal solution?

Answer 1

What you ask is to decide whether a given coin system is canonical for the change problem. A system is canonical if a greedy algorithm always gives an optimal solution. You can decide whether the coin system, which includes a 1-cent piece, is canonical or not in a finite number of steps. Details and more efficient algorithms in some cases can be found at http://arxiv.org/pdf/0809.0400.pdf .