How to solve Coins problem in C

[vishalonne]

Hello

How can I get minimum number of coins for a given amount.
I have fixed denominations of cents - 25, 10, 5 and 1
If I have 0.67 then what will be the minimum numbers coins I need

Thank you all in advance for valueable advices and suggestions

[rubberman]

Class assignment? Sorry, but the terms of service here do not allow us to do your homework for you. Make a good attempt to solve the problem, and if you have errors, post the code here, which we can then critique and help you with (to a point).

[Gonbe]

You can construct the value of any coin, using coins of lower value (if there are any); this makes the problem easier because the smallest amount of coins required is then obtained by repeatedly paying with the highest value coin, until the remaining cost is 0 (it would be diffent if the coins had different values, e.g. 80, 45 and 1. If you'd then want to pay a value of say 90, you don't want to fit the biggest, because that would result in one coin of 80 and 10 coins of 1 instead of the better solution: 2 coins of 45. Relevant reading material: http://en.wikipedia.org/wiki/Knapsack_problem)

Think of the $0.67 as the size of a "space" you need to fill with the fixed denominations. Start with the largest denominations. Use the modulus (%) operator to figure out how many of them can fit in the space. Then, if the space is not completely filled, move to the next largest denomination and repeat.