CODEWITHSUNDEEP
algorithmdynamic-programminggreedy
bhavya
bhavya

Reputation: 169

Coin Change : Greedy Approach

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?

Upvotes: 6

Views: 3288

Answers (1)

Edward Doolittle
Edward Doolittle

Reputation: 4100

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.

Upvotes: 1

Related Questions