算法来确定给定的价格“通常”现金支付金额
https://stackoverflow.com/questions/302406
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
您走进一家商店，选择一些产品，然后去柜台支付你的账单。合计为一定量（A）。你往你的钱包，钱包或口袋放下一些现金（P），其中P[1]> = P[2]，和收银员给你更改。
P[3]？最有可能的值
一些例子，假定可用的纸币是$ 5，$ 10，$ 20 $ 50和$ 100，并且可用的硬币是图5c，10c和25c的：
<=> = $ 151.24，点击<=> = $ 160（8×20 $）或（$ 100 + 3×$ 20），点击<=> = $ 155（$ 100 + $ 50 + $ 5）
<=> = $ 22.65，点击<=> = $ 25（$ 20±$ 5），点击<=> = $ 30（$ 600 + $ 10），点击<=> = $ 40（$ 20±$ 20）
<=> = $ 0.95，点击<=> = $ 1（4×25℃），点击<=> = $ 5'/ P>
许多这些数字似乎直观，但是我有一种感觉，该算法是很难牵制。
解决方案
有也其他因素，则不太可能与6×0.25支付，将使用1×1.00和2×0.25代替。通常0.25就没有更多然后3，0.10就没有超过2，和0.05就没有更多然后1。
此外，在现实世界中，许多人从来没有打扰值小于1.00时，他们alawys与账单支付和“不用找了”。
同样适用于5.00，10.00，20.00，用于购买更多的则一两块钱的人会使用5.00或10.00代替。当然20.00是最常见的流通由于ATM机。
这是什么软件？你实际上是试图模型实际购买，并且需要准确的结果，或者是没有一个简单的模拟是很严格？
其他提示
“最有可能”使这是一个非常棘手的问题。您需要了解每种类型的货币的相对可用性和分配。例如，在循环的所有纸币的22％是20多岁的$，使它们更有可能低于$ 10或$所用票据50 $ 10 $和100之间的量。
这实际上是一个已知的问题，这是 binpacking 的变体，如果我不误...
有时它被称为收银员算法（或贪婪算法）。你可以找到在此演示文稿的实现： HTTP：// WWW。 cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf ，见11/12/13页..
（澄清，正常收银员算法只需要返回支付客户回币的最小量，但你可以改变动态规划的解决方案来计算所有可能的组合）
OH！@＃$％^＆*（）_，我现在真的pi..ed。
我刚写的伪代码和复杂性估计为10分钟，当我张贴有刚刚按钮“我是一个人”没有任何机会进入的东西，我的整个后消失（当然，这次我没有做编辑窗口的副本，以防万一......），好吧所以这里是短版：
硬币的数量通常超级单调（即每个值是>比以前的值的总和），为此可以使用贪婪得到确切的硬币为甲
现在使用的硬币的该多组P，将其添加到（到现在是空的）结果集（一组多重集的），并以（到现在空的太）工作集。
现在重复，直到工作集是空的：
径设定P输出工作集，P的 '= P，对P中的每个硬币C：P'= P.replace（C，nextBiggerCoin），removeSmallestCoin（只要为P而不仍然最小硬币> A）
如果所述P”是尚未在结果集，把它放入结果集和工作集
我猜到复杂度O（S * N ^ 2），其中s的解决方案的数量。
有用于点销售的系统。当计算出最终价格，收银员在由客户提供的现金数额进入。有应被设置为“可能”金额，以出纳的生活更轻松三“快捷键”按钮。绝对的完美是没有必要的。 - eJames（11月19日22点28处）
我不认为这是一个完美的算法这一点。如果我是你，我会找到现有的POS数据源进行大量现金交易和评估，超过价格的特定范围。找人平时如何支付价格的具体范围（零钱更有可能），并制定出最适合的配方为最有区别的范围。
实际上，我是谁最终实现这一个人，所以我想最好还是发布最终结果。它不漂亮，但它的快速和没有任何循环或数组。我不认为这是概念问题的解决方案，但它确实解决了实际问题。
在大多数情况下，实际使用被限制在$ 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票据的可能性越大。
该算法还很好地扩展到$ 100至$ 200系列。以上说的是在零售一个罕见的情况。
