好久没出思考题了，前几天我从微信公众号“超级数学建模”上看到了一个报道，说加拿大滑铁卢大学计算机系研究员（这个系就是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 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的计算是否正确吧， :)
