好久没出思考题了，前几天我从微信公众号“超级数学建模”上看到了一个报道，说加拿大滑铁卢大学计算机系研究员（这个系就是Maple的诞生地哈！）Jeffrey Shallit通过数学建模解出来我们现在的货币组合方式——1元、5元、10元、20元、50元——效率并不好，他算出使用1元、5元、16元、23元、33元这种面额的钞票是最佳的，因为同样是通过面值组合形成1~99元，按他给出的新组合，平均仅需要3.29张。
嗯，公众号里的插科打诨我就不抄了，只说题面，希望各位通过自己的建模来检验一下Jeffrey Shallit的计算是否正确：
平时我们去超市买东西，每次使用100元一下数额的钱（1元到99元），需要用1元、5元、10元、20元、50元五种面额的铅笔组合而成，有的时候需要一张，有的时候需要两张或更多。比如你需要31元的零钱，可以用三张10元和一张1元，也可以用一张10元、一张20元和一张1元，前一种需要四张纸币，后一种需要三张。在组成31的所有可能方案中，10+20+1是最佳的，它最节省钞票张数，也就是说，凑成31元最少也需要三张纸币。
我们可以对1到99之间的每个数额分别算出来它最少需要的纸币张数，这不难通过编程实现。这样一来就能知道使用这五种面额的人民币组成99个数额，在最“环保”的组合方式下，平均需要多少张纸币。
Jeffrey在电脑上把参数修改了一下，五种纸币的面额更改为各种其他数值，让电脑程序运行，看一看哪一种货币面额体系在组成99个数额的时候平均最方便、需要的纸币张数最少。形成了下面的表：
Jeffrey的思路在题面里也说得很明白，根据这条思路也给出了他的计算结果，公众号里说这是他发表于2003年的一篇论文中的数据。好了，各位，尝试着自己建一个模型来验证Jeffrey的计算是否正确吧， :)

剑客，好！
腾出手来了？
我不擅排列组合题，静看各位老师的高招把。

这个不是排列组合问题，我自己试着编了一次，用递归和穷举就可以解决这个问题。
我觉得觉得这个问题原来我怎么没想到呢哈，说来还是我在实际生活中对数学的敏感性不高吧。

现在还不是有时间了，可能要到今年的九月份之后才能真正的恢复前两年的状态。

我自己编程试了一下，感觉Jeffrey的结果可能是错的。对于他提出来的那个最佳组合，我得到的平均张数是：4.152，而不是3.29张。如下：
我还没有继续往下编，不过从这个结果上看，我估计我能得到与Jeffrey不同的面额组合了。

呵呵，因为这里面涉及到的矩阵不是很大，MC运算起来倒是没什么压力。

我把我得到的面额组合矩阵仔细看了一遍，没发现错误，那么Jeffrey的那个3.29就很可疑了。
最近这段时间我看的文献比较多，渐渐的也学会了怀疑那些已经发表了的结论，往往会有很有意思的收获哈……看来这次也不例外。

我把Jeffrey的所有结果都验算了一遍，然后发现上面的那个表里没有一个是对的……
不过结论是对的，也就是Jeffrey给出的那个最佳组合确实比我们传统的钞票面额组合在平均需要的张数上要少一点。

张数为2的情况：

哈哈，刚刚编的工作簿。我觉得是排列组合问题，结论可能有问题。

记得有书解释过，币面值为什么要用质数，理由就是能使组成币数值的币的张数最少。所以，对于Jeffre的理论，存疑。
我编得程序如下：
人民币RMB的平均张数是3.434
Jeffre的平均张数是4.152

第5套人民币：
平均张数4.242