SOLUTION: Where can I find an algorithm to determine the minimum number of nickels, dimes, quarters and dollar bills required to give change for a dispensed product, like in a Coke machine?

Question 271679: Where can I find an algorithm to determine the minimum number of nickels, dimes, quarters and dollar bills required to give change for a dispensed product, like in a Coke machine? I am writing a programin VBA for Excel that simulates the functions of a Coke machine and need to understand how much of each denomination is required. I expect it would vary depending on the amount of the product sold, and it seems like this should be a problem that has been solved as there are millions of vending machines around which give change. The machine will turn on an exact change only light when the coins in the machine fall below the threshold value.
Answer by jim_thompson5910(35256) (Show Source): You can put this solution on YOUR website!
I'm not sure of the exact algorithm, but I would expect that the program would try to dispense the largest denominations possible (that are less than the amount of change required) and then work it's way down.

For example, if the machine is going to dispense 37 cents, it would first dispense a quarter (25 cents) since this is the largest denomination that is less than 37 cents. So 37-25 = 12 cents remain. Next up would be a dime (10 cents) since this is the largest coin under 12 cents. So 12-10 = 2 cents remain. Finally, the only choices left are 2 pennies. So four coins would be dispensed.
RELATED QUESTIONS
How can I use all of these monies at the same time to equal up to $70? One dollar bills (answered by JulietG)

In a purse are nickels, dimes and quarters amounting to $9.85. There are twice as many... (answered by josgarithmetic)

A person has quarters, dimes, nickels,and pennies with a total value of $3.86. The... (answered by jim_thompson5910,richwmiller)

I'm having a bit of trouble figuring out the correct algorithm for this problem:... (answered by richwmiller)

How many different ways can nickels, dimes, and quarters be combined to total one... (answered by midwood_trail)

A person has quarters, dimes, nickels, and pennies, with a total value of $3.86. The... (answered by scott8148)

A collection of nickels dimes and quarters amount to $10.00 there are 140 coins and there (answered by ikleyn)

i need help. write a system of equations. an errand boy went to deposit some bills (answered by htmentor)

You have quarters, dimes and nickels with a total value of 500 cents or $5.00. The... (answered by stanbon)