This code golf question got me thinking.
I wasn't even aware that the Cashier's Algorithm was a formal thing.
Reading it, and Googling around, I see that all solutions seem to concern themselves with paying out the fewest number of coins.
I wondered if vending machines operate exactly that way, or if they think “uh, oh! I'm running low on quarters; better hold some back & give out five nickels instead”.
Does anyone know the algorithm used? I would also like to ask for an optimal algorithm, but am not sure if that would be considered opinion based, so I will just settle for how it is actually done, if anyone has experience.
Is it a straightforward cashier’s algorithm, or something else?
Best Answer
Vending machines go "Uh, oh! I'm out of quarters. Better start giving out dimes and nickels instead."
For the US system of money, a greedy algorithm (one in which you choose the largest available coin that is still less than the remaining change) always produces the smallest number of coins.