3

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?

Improve this question
0

1 Answer 1

Reset to default
5

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.

Improve this answer
3
  • +1 I used US currency because most of the users of this site are our Colonial cousins. I would have preferred to ask for a general algorithm, but was afraid of the "that's an opinion" police. Btw, despite my upvote, you have entirely missed the point of the question, which is something like - "all published articles posit an infinite number of each denomination - what happens In Real Life, when some denominations are missing, scarce or overly abundant". Fell free to post another answer :-)
    – Mawg says reinstate Monica
    Oct 14, 2016 at 19:56
  • 2
    In real life, the greedy algorithm still works, regardless of the relative abundance or scarcity of particular coins. Alternative algorithms are reserved for hypothetical coin systems, and are therefore only interesting in the abstract (unless you happen to know of a modern coin system that is not based on 1's, 5's & 10's).
    – Robert Harvey
    Oct 14, 2016 at 19:58
  • 3
    @RobertHarvey: I think there are systems that have 0.50, 0.25, 0.10 and 0.05 coins, where greedy algorithm wouldn't work (if you need to return 0.30 and have plenty of 0.25 and 0.10 but no 0.05 coins). One example would be the USA.
    – gnasher729
    Oct 15, 2016 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.