Coin Change : Greedy Approach

Question

The Problem is making n cents change with quarters, dimes, nickels, and pennies, and using the least total number of coins. In the particular case where the four denominations are quarters,dimes, nickels, and pennies, we have c1 = 25, c2 = 10, c3 = 5, and c4 = 1.

If we have only quarters, dimes, and pennies (and no nickels) to use, the greedy algorithm would make change for 30 cents using six coins—a quarter and five pennies—whereas we could have used three coins, namely, three dimes.

Given a set of denominations, how can we say whether greedy approach creates an optimal solution?

Galilean

Are you asking how to solve this? There's a simple dynamic programming solution for it. – Mosher

@AmiTavory I was Reading discreet mathematics and It's applications by Rosen and he had cited this example in his book. Even i thought the problem to be similar to the Knapsack problem and Was surprised at a greedy solution – Galilean

Sorry, but (at least) I just don't understand what exactly you're asking. Perhaps you could edit your question a bit. – Mosher

@AmiTavory He's asking for a sufficient condition that if given, greedy approach to coin change is optimal – Donets

Ah, I was thrown off a bit by "It the greedy approach suitable for this problem.". Can't edit the question, for some reason (perhaps someone else (you?) is doing so). – Mosher

@Galilean Have a look here – Mosher

Answer 1

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

Ross