Algorithm to determine the "usual" cash payment amounts for a given price

Question

You walk into a store, select several products, then go to the counter to pay your bill. The total is some amount (A). You reach into your wallet, purse, or pocket and put down some cash (P), where P >= A, and the cashier gives you change.

Given the set of coins and bills that are in circulation, what are the most likely values for P?

Some examples, assuming that the available bills are $5, $10, $20, $50 and $100, and the available coins are 5c, 10c and 25c:

A = $151.24
P[1] = $160 (8x$20) or ($100 + 3x$20)
P[2] = $155 ($100 + $50 + $5)

A = $22.65
P[1] = $25 ($20 + $5)
P[2] = $30 ($20 + $10)
P[3] = $40 ($20 + $20)

A = $0.95
P[1] = $1 (4 x 25c)
P[2] = $5

Many of these numbers seem intuitive, but I have a feeling that the algorithm is difficult to pin down.

Answer 1

There are also other factors, you are not likely to pay with 6 x 0.25, you would use 1 x 1.00 and 2 x 0.25 instead. Generally 0.25 would be no more then 3, 0.10 would be no more then 2, and 0.05 would be no more then 1.

Also in the real world, many people never bother with values less then 1.00, they alawys pay with bills and "keep the change".

Same applies to 5.00, 10.00, and 20.00, for purchases more then a couple of dollars people will use a 5.00 or 10.00 instead. Of course 20.00 are the most common in circulation thanks to ATM machines.

What is this software for? are you actually trying model actual purchases and need accurate results, or a simple simulation which does not have to be rigorous?

Answer 2

It is for a point-of-sale system. When the final price is calculated, the cashier has to enter in the amount of cash provided by the customer. There are three "shortcut" buttons which should be set to the "likely" amounts to make the cashier's life easier. Absolute perfection is not necessary. – eJames (Nov 19 at 22:28)

I do not think there is a perfect algorithm for this. If I were you, I would find a source of existing POS data for a large number of cash transactions and evaluate that over particular ranges of prices. Find how people usually pay for specific ranges of prices (exact change is far more likely ), and work out a best-fit formula for the most differentiated ranges.

Answer 3

This is actually a known problem, it's a variant of binpacking if I'm not mistaken...

Sometimes it's called the cashiers algorithm (or greedy algorithm). You can find an implementation in this presentation: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf , see page 11/12/13..

(to clarify, the normal cashiers algorithm only returns the minimal amount of coins needed to pay the customer back. But you could change the dynamic programming solution to calculate all the possible combinations)

Answer 4

OH !@#$%^&*()_, now I am really pi..ed.

I just wrote pseudocode and complexity estimation for 10 minutes, and when I post there is just the button "I am a human being" without any opportunity to enter something and my complete post is gone (and of course, this time I did not make a copy of the edit window, just in case ...), ok so here are the short version:

Number of Coins usually super monotone (i.e. each value is > than sum of previous values), therefor you can use greedy to get the exact coins for A.

Now use this multi set P of coins, add it to the (up to now empty) result set (a set of multisets), and to the (up to now empty too) working set.

Now repeat until the working set is empty:

Take set P out of the working set, P' = P, for each coin c in P: P' = P.replace(c, nextBiggerCoin), removeSmallestCoin(as long as P without smallest coin still > A)

If the P' is not yet in result set, put it into result set and working set

My guessed complexity was O(s*n^2), with s the number of solutions.