确定“通常”的算法 给定价格的现金支付金额
您走进一家商店，选择几种产品，然后去柜台支付账单。 总数是一定数量 (A)。 您把手伸进钱包、钱包或口袋，放入一些现金 (P)，其中 P >= A，收银员给你零钱。
给定一组流通的硬币和纸币，P 最可能的值是多少？
一些示例，假设可用纸币为 $5、$10、$20、$50 和 $100，可用硬币为 5c、10c 和 25c：
A = $151.24P[1] = $160 (8x$20) 或 ($100 + 3x$20)P[2] = $155 ($100 + $50 + $5)
A = $22.65P[1] = $25 ($20 + $5)P[2] = $30 ($20 + $10)P[ 3] = $40 ($20 + $20)
A = $0.95P[1] = $1 (4 x 25c)P[2] = $5
其中许多数字看起来很直观，但我有一种感觉，该算法很难确定。
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.24P[1] = $160 (8x$20) or ($100 + 3x$20)P[2] = $155 ($100 + $50 + $5)
A = $22.65P[1] = $25 ($20 + $5)P[2] = $30 ($20 + $10)P[3] = $40 ($20 + $20)
A = $0.95P[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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
还有其他因素，您不太可能支付 6 x 0.25，您会使用 1 x 1.00 和 2 x 0.25 代替。 一般来说，0.25 不超过 3，0.10 不超过 2，0.05 不超过 1。
同样在现实世界中，许多人从不关心小于 1.00 的值，他们总是用账单付款并“保留”改变”。
同样的情况也适用于 5.00、10.00 和 20.00，对于购买超过几美元的商品，人们会使用 5.00 或 10.00。 当然，由于 ATM 机的存在，20 点是流通中最常见的。
这个软件是做什么用的？ 您实际上是在尝试对实际购买进行建模并需要准确的结果，还是不需要严格的简单模拟？
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?
“最有可能”使这成为一个非常棘手的问题。 您需要了解每种货币的相对可用性和分布。 例如，所有流通中的纸币中有 22% 是 20 美元，这使得 20 美元纸币比 10 美元或 50 美元纸币更有可能被使用，金额在 10 美元到 100 美元之间。
"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.
这实际上是一个已知问题，如果我没记错的话，它是 binpacking 的变体。 。
有时它被称为收银员算法（或贪婪算法） 您可以在此演示文稿中找到一个实现：http://www. cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf，参见第 11/12/13 页..
（澄清一下，正常的收银员算法仅返回支付给客户所需的最小数量的硬币但您可以更改动态规划解决方案来计算所有可能的组合）
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)
哦！@#$%^&*()_，现在我真的很开心。
我只是写了 10 分钟的伪代码和复杂性估计，当我发帖时，只有“我是一个人”按钮，没有任何机会输入任何内容，我的完整帖子就消失了（当然，这次我没有做编辑窗口的副本，以防万一...），好的，这里是简短的版本：
硬币数量通常超级单调（即每个值大于先前值的总和），因此您可以使用贪婪来获得A 的确切硬币。
现在使用这个多组 P 硬币，将其添加到（到目前为止为空）结果集（一组多重集）和（到目前为止也为空）工作集。
现在重复直到工作集为空：
从工作集中取出集合 P，P' = P，对于 P 中的每个硬币 c：P' = P.replace(c, nextBiggerCoin)，removeSmallestCoin（只要 P 没有最小的） coin still > A)
如果 P' 尚未在结果集中，则将其放入结果集和工作集中
我猜测复杂度为 O(s*n^2)，其中 s 为解数。
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.
我认为对此没有完美的算法。 如果我是您，我会找到大量现金交易的现有 POS 数据源，并在特定的价格范围内对其进行评估。 找出人们通常如何支付特定价格范围（精确变化的可能性要大得多），并为最差异化的范围制定最适合的公式。
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.
实际上我是最终实现这个的人，所以我认为最好发布最终结果。 它不漂亮，但速度很快，并且没有任何循环或数组。 我不认为这是概念问题的解决方案，但它确实解决了实际问题。
在大多数情况下，实际使用量限制在 5 美元到 200 美元的范围内。 大多数人通常不会定期提取 500 美元现金:)
我决定研究从 0 美元到 5 美元、5 美元到 10 美元的各种情况。 。 。 45 美元到 50 美元。 我们有 3 个按钮，因此在每种情况下，第一个按钮（最低）将是价格上方下一个 5 美元的值。 因此，如果是 7.45 美元，那么第一个按钮就是 8 美元，13.34 美元 -> 3 美元。 15 美元，21.01 美元 -> 25 美元。
剩下第二个和第三个按钮。 考虑到 5 美元、10 美元、20 美元、50 美元钞票的标准价值，每个案例都有明显的答案。 例如：查看 $24.50，然后 1->$25、2->$30、3->$40。 这些可以通过表格和一些常识找到。
我还发现使用大于 50 美元的值可以简单地匹配低于 50 美元的值。 即：$72.01 与 $22.01 的答案相同，依此类推。 唯一需要注意的是数字大于 60 且小于 70。这种情况需要处理 4 张 20 美元钞票的可能性。
该算法还可以很好地扩展到 100 美元到 200 美元的范围内。 以上是零售业的罕见案例。
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.