Algorithm to determine the “usual” cash payment am

问题:

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.

回答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?

回答2:

"Most likely" makes this a very tricky problem. You would need to know the relative availability and distribution of each type of currency. For example, 22% of all bills in circulation are $20s, making them far more likely to be used than $10 or $50 bills for amounts between $10 and $100.

回答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)

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

回答5:

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.

回答6:

I was actually the person who ended up implementing this one so I thought it best to post the end result. It's not pretty but it's quick and doesn't have any loops or arrays. I don't consider this a solution to the conceptual question but it does solve the practical problem.

In most situations, the actual usage is limited to the $5 to $200 range. Most people don't usually pull out $500 in cash on a regular basis:)

I decided to look at the various cases from $0 to $5, $5 to $10, . . . $45 to $50. We had 3 buttons so in every case, the first button (lowest) would be the next $5 value above the price. So if it was $7.45 then $8 was the first button, $13.34 -> $15, $21.01 -> $25.

This leaves the 2nd and 3rd buttons. Each case has obvious answers given the standard values of $5, $10, $20, $50 bills. eg: Looking at $24.50 then 1->$25, 2->$30, 3->$40. These can be found using a table and some common sense.

I also found that using values greater $50 could simply match their below $50 counterparts. ie: $72.01 would be the same answer as $22.01, and so on. The only caveat is with numbers greater than 60 and less than 70. That case requires handling the possibility of 4 $20 bills.

The algorithm also scales nicely into the $100 to $200 range. Above that is a rare case in retail.