回复：【思考题】最佳的货币面值组合方式

在
http://tieba.baidu.com/p/3216612201
中，我用矩阵的裁剪拼贴的方法得到全组合的方法，其中用到了递归。
这回因为这道题中对组合的奇怪要求，反倒使我得到另外一种计算全组合的方法，没有用到递归。

嗯，Tc（）是对任何长度的向量，对给定的元素数（m）和取出元素数（n）给出在该向量相对“下一级”的两元素全组合，Mtc（）是用第一个函数进行迭代，最终得到给定元素数和取出元素数的全组合。
不过这个迭代的方法的运行效率很差劲，没有原来的那个递归的方法有效，运行速度慢，而且不能处理比较大的全组合问题。
我现在在想办法在解决Jeffrey问题的过程中，避免出现对全组合遍历，而仅仅使用穷举，这样可以避免在过程中出现非常大的矩阵——就向我前面解决（99，2）的那样。
@loupoo2 ，我比较关心的是你的评价，你认为他得到的那个“3.29”合理吗？我感觉不合理。
@月城公寓寓公 ，你的程序如果方便上传一份，我感觉结果也很奇怪。

Jeffrey的问题特殊的地方是，你得到的所有组合都必须有1。也就是说最后得到的全组合的矩阵是：stack(1,xxx)这样的形式。

我编的程序：
链接: http://pan.baidu.com/s/1bCTGUa 密码: gmew
loupoo2老师说用递归是错误的，我没想明白。

嗯，我明白了，你用的是RMB系统，1，2，5，10，20，50来算的哈！不过，用现在的货币面额组合，6种面额的情况，看来还是比Jeffrey的结果要好，他给出的那两个组合我算出来是3.567和3.758，而Jeffrey给出的是2.92。
从@Loupoo2 给出的结果看，我还是没弄明白Jeffrey为什么会用7个元素的向量，并且在没有面额填充的向量值中要填上100。Loupoo2你能解释一下么？

还有@月城公寓寓公 ，现在还有2元的RMB吗？我是说近5年，我就没见过2元的RMB了，你给张照片了？ :P

我刚刚扫描的：

初步的验算结果是Jeffrey的最佳钞票面额组合好像完全错了。
@Loupoo2 我没看明白你的那个在一定货币面额组合下求其最小平均张数的程序，真的很想知道你的思路。
主要是我验算我这边儿的程序，而且把结构一一检查了一下，没发现哪里计算错了，但是就是没有得到Jeffrey的结果。
我按照我的思路得到的初步结果是这样的：
（1）用给定的货币面额组合，要凑足一定数额的钱，所需要的最小张数是多少。

（2）用给定货币面额的组合，凑足1~99所有数额的钱，最小张数的平均是多少。

（3）这是一个过程公式，做组合用的。

（4）给定最大的数额m，给定张数n，最佳的货币组合是什么。

（5）我编的这个程序的处理效率还是太低，主要是想做到穷举而不遍历，又不想把程序编得太蠢（实际上用嵌套的for循环应该可以做到），结果还是大矩阵的计算了，那就是几百万的大矩阵，很失败。所以这里只给出2种、3种、4种货币组合的结果，5种货币到现在还没算出来呢 :(

嗯， 还有一个法子就是我说的比较蠢的那个——对每一种货币额度数量单独做程序，这样计算速度会稍快一些，因为根本进出现了大循环，没有出现大矩阵，省了一些内存资源。
给出前3个，后面的几个都一样，以此类推就可以了。我没找到怎么把这些相似的明显有规律的程序给整合成1个更智能一些的程序。



嗯，Ntc5、Ntc6、Ntc7都一样。
希望有兴趣的吧友试试看，用迭代或者递归，还是什么法子，使具有这样嵌套for循环的式子变成1个程序。这是件功德无量的事儿！
用这个方法我比较快的算出了Ntc5，用来大概有半小时吧。

ntc6我让机器开了一晚上，第二天早晨起来看仍旧没有出结果呢。算了一下它的组合数，7千万！嗯，ntc7特么有11亿！

我觉得这道题肯定不是用全组合傻算的法子来这么暴力破解的。

@Loupoo2 谢谢哈，你的思路确实好许多。相比之下，我就是个搬砖的……

在网上搜了一下，这类题要用动态规划的方法。
现学现卖，把我的程序修改了。计算耗时数秒，没有用time()。
Jeffre的平均张数是3.323

又多了一个平均所需张数……@月城公寓寓公 ，我觉得验算对一定的货币面额种类组成1~99的平均张数的最简单可靠的办法是把程序计算出来的那些最佳组合一一列出来，一共是99个，从头到尾看一遍，也花不了多长时间，结果是否合理也就很明白了。
嗯，我的那个全组合遍历的方法确实很笨，用Loupoo2的最小公倍数的思路循环次数就会少多了。

为什么他还要乘以0.99呢？

我刚才有上传了一次矩阵图，又被删掉了。
把我28楼的程序板中的最后一个语句tirm()删除，结果就是这样：