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.
|
|
|
