Returning change algorithim

Question

I am trying to write a C program for a vending machine, and I'm stuck in making change after deducting the price.

The steps are as follows

• Enter amount of money: 5
• Select an item: 1
• Get your item! Change: 4

this is when i still have coins. So after the coins finish, the program should do this:

• Enter amount of money: 2
• Select an item: 4 //the price of the item is 1
• Get your item!No 1s left! 2, 0.5 are used!
• Change:1

I am stuck in the way of knowing the change, how to determin wether 3 0.5s will be returned or 30 0.05s? .

note:Please don't give me any code, i want to do it by my self, only algorithim.

Answer 1

Use the a greedy algorithm. Not optminal, but but the idea is very simple: while there's a remaining amount of change to return, pick the largest available denomination of coin which is less or equal to that remaining amount. After picking each coin, substract the chosen coin value from the remaining amount and decrement the available number of coins of that denomination.