5

你走进一家商店，选择几种产品，然后去柜台付帐。总金额为（A）。你把手伸进钱包、钱包或口袋，放下一些现金 ( P)，其中P>= A，收银员会给你找零。

给定流通中的一组硬币和纸币，最可能的值是P多少？

一些例子，假设可用的钞票是 5 美元、10 美元、20 美元、50 美元和 100 美元，可用的硬币是 5c、10c 和 25c：

A= $151.24
P[1]= $160 (8x$20) 或 ($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

其中许多数字看起来很直观，但我感觉算法很难确定。

4

6 回答 6

2

“最有可能”使这是一个非常棘手的问题。您需要了解每种货币的相对可用性和分布情况。例如，流通中的所有纸币中有 22% 是 20 美元，这使得它们比 10 美元或 50 美元的纸币更可能用于 10 美元到 100 美元之间的金额。

于 2008-11-19T21:42:52.123 回答
2

这实际上是一个已知问题，如果我没记错的话，它是binpacking的一种变体......

有时它被称为收银员算法（或贪心算法）。您可以在此演示文稿中找到一个实现：http ://www.cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf ，参见第 11/12/13 页。

（澄清一下，正常的收银员算法只返回支付客户所需的最小数量的硬币。但您可以更改动态编程解决方案来计算所有可能的组合）

于 2008-11-19T21:56:58.633 回答
2

还有其他因素，您不太可能用 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.00 是流通中最常见的。

这个软件是干什么用的？您实际上是在尝试模拟实际购买并需要准确的结果，还是一个不需要严格的简单模拟？

于 2008-11-19T22:13:18.443 回答
1

哦！@#$%^&*()_，现在我真的很生气。

我只写了10分钟的伪代码和复杂度估计，当我发帖时只有“我是人”按钮，没有任何机会输入内容，我的完整帖子不见了（当然，这次我没有做编辑窗口的副本，以防万一...），好的，这是简短的版本：

硬币数量通常是超单调的（即每个值都大于先前值的总和），因此您可以使用贪心来获得 A 的确切硬币。

现在使用这个多组 P 硬币，将其添加到（到目前为止为空的）结果集（一组多重集）和（到目前为止也是空的）工作集。

现在重复直到工作集为空：

将集合 P 从工作集中取出，P' = P，对于 P 中的每个硬币 c： P' = P.replace(c, nextBiggerCoin)，removeSmallestCoin(只要 P 没有最小的硬币仍然 > A)

如果 P' 尚未在结果集中，则将其放入结果集和工作集中

我猜测的复杂度是 O(s*n^2)，其中 s 是解决方案的数量。

于 2008-11-19T17:44:57.097 回答
1

它适用于销售点系统。计算最终价格时，收银员必须输入客户提供的现金金额。应该将三个“快捷方式”按钮设置为“可能”金额，以使收银员的生活更轻松。绝对完美是不必要的。– eJames（11 月 19 日 22:28）

我不认为有一个完美的算法。如果我是你，我会找到大量现金交易的现有 POS 数据来源，并在特定价格范围内对其进行评估。找出人们通常如何为特定的价格范围付费（确切的变化更有可能），并为最差异化的范围制定最合适的公式。

于 2008-11-25T03:28:29.493 回答
1

我实际上是最终实施这个的人，所以我认为最好发布最终结果。它不漂亮，但它很快并且没有任何循环或数组。我不认为这是对概念问题的解决方案，但它确实解决了实际问题。

在大多数情况下，实际使用限制在 5 美元到 200 美元之间。大多数人通常不会定期取出 500 美元现金：）

我决定查看从 0 美元到 5 美元、5 美元到 10 美元的各种案例。. . 45 到 50 美元。我们有 3 个按钮，所以在每种情况下，第一个按钮（最低的）将是高于价格的下一个 5 美元的价值。所以如果是 7.45 美元，那么第一个按钮就是 8 美元，13.34 美元 -> 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 美元钞票的可能性。

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

于 2009-02-20T17:06:35.737 回答