您走进一家商店，选择几种产品，然后前往柜台支付账单。总额是一些金额（A）。你到达你的钱包，钱包或口袋里，并放下一些现金（P），其中P> = A，收银员给你改变。确定给定价格的“通常”现金支付金额的算法
给定一套正在流通的硬币和账单，P最可能的值是什么？
一些例子，假定可用的纸币是$ 5，$ 10，$ 20 $ 50和$ 100，并且可用的硬币是图5c，10c和25c的：
A = $ 151.24 P[1] = $ 160（8×$ 20）或（$ 100 + 3×$ 20）P[2] = $ 155（$ 100 + $ 50 + $ 5）
A = $ 22.65 P[1] = $ 25（$ 20±$ 5）P[2] = $ 30（$ 600 + $ 10）P[3] = $ 40（$ 20±$ 20 ）
A = $ 0.95 P[1] = $ 1（4×25℃）P[2] = $ 5
许多这些数的好象直观，但是我有一种感觉，该算法是困难的牵制。
还有其他的因素，你是不是有可能与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机中最常见的流通。
这是什么软件？你是否真的试图模拟实际购买并需要准确的结果，或者一个简单的模拟不需要严格？
OH！@＃$％^ & *（）_，现在我真的被盗用了。
我刚刚写了10分钟的伪代码和复杂度估计，当我发布时，只有按钮“我是人”，没有任何机会输入内容，我的完整文章已经消失了（当然，这一次我没有制作编辑窗口的副本，以防万一...），好的，下面是简短版本：
硬币的数量通常超单调（即每个值大于以前的值的总和），因此，您可以使用贪婪来获得A的确切硬币。
现在使用这个多集P的硬币，将它添加到（现在为空）结果集（一组multisets），并将到现在也是空的）工作集。
现在重复直到工作集是空的：
采取集P出来的工作集的，P '= P，对P中的每个硬币C：P'= P.replace（C，nextBiggerCoin）， removeSmallestCoin（在P没有最小的硬币仍然> A）
如果P”还没有在结果集中，把它放入结果集和工作集
我猜复杂度D（S * N^2），其中s是解决方案的数量。
“最有可能”使这成为一个非常棘手的问题。您需要知道每种货币的相对可用性和分布情况。例如，流通中所有票据中有22％是20美元，这使得他们使用10美元或50美元以上的票据的可能性大于10美元至100美元。
这实际上是一个已知的问题，它是binpacking的一个变种，如果我没有弄错的话......
有时这就是所谓的收银员算法（或greedy algorithm）。您可以在本演示中找到一个实现：http://www.cs.princeton.edu/~wayne/kleinberg-tardos/04greed.pdf，请参阅第11/12/13页。
（为了澄清，普通收银员算法仅返回支付客户所需的最小金额数额，但您可以更改动态规划的解决方案来计算所有可能的组合）
这是一个点的销售系统。当计算最终价格时，收银员必须输入客户提供的现金数额。有三个“快捷方式”按钮应设置为“可能”的数量，以使收银员的生活更轻松。绝对完美是没有必要的。 - 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美元。
这会留下第2个和第3个按钮。鉴于标准价值5美元，10美元，20美元，50美元的账单，每种情况都有明显的答案。例如：看$ 24.50，然后1 - > 25美元，2 - > 30美元，3 - > 40美元。这些可以使用表格和一些常识来找到。
我还发现，使用值大$ 50可以简单地满足他们的低于50 $同行。即：72.01美元与22.01美元的答案相同，以此类推。唯一需要注意的是数字大于60且小于70.这种情况下需要处理4美元20美元的可能性。
该算法也很好地扩展到100美元到200美元的范围内。以上是零售业中罕见的情况。
几年前，我做了一个这样的小项目。但我不确定你的意思是我的“平常”。在我的项目中，我们想知道根据赌注和球员人数来兑现一组扑克玩家所需的最小数量的纸币和硬币。 – benjismith 2008-11-19 16:12:40
我同意“通常”会有所不同......当我携带现金时，我从不携带任何大于20的东西。我知道携带50以下的任何人（因此他们不买小事）。如果你正在寻找最少的账单情况，一个标准的贪婪算法至少可以用美国货币来做 – warren 2008-11-19 16:25:29
是的，这种“通常”的要求会让这种情况变得困难。 – 2008-11-19 17:24:10