2014新年元旦第一强帖：实用凑数凑金额高效递归剪枝算法

香川群子

最近发现、各种凑数、凑金额的求助帖还是比较多。

有人建议用规划求解……
但缺点是显而易见的：
源数据个数较多时计算很长时间不会有结果；往往不能精确匹配；只能给出一组近似解……


也有人亲力而为，为求助者写循环代码计算出结果了……
计算效率非常之低就不说了，显然不具有通用性，应该是属于吃力不讨好的工作。


…………
我因为彭版出过的一道求1-100总和=100的所有组合解（共444,793个）的帖子，
所以研究了速度最快的递归组合求和算法。

后来发现这个题目很有实用价值，用来解决凑数、凑金额问题，几乎是手到擒来。


但是考虑到实际需求，于是又不断做了很多改进（牺牲了一些计算速度效率），
但实用性大为提高，最后得到的程序功能之多之全、功力之大，前所未见。


趁着今天休息在家，就把程序重新整理了一遍、并且加了一些简要的注释，把代码公开。
希望能给大家一个惊喜！
凑数字凑金额的最佳递归程序by_kagawa.rar (26.84 KB, 下载次数: 14089)

2014-1-9 21:13 上传

点击文件名下载附件

附件做了一次更新……递归计算深度参数的设置做了改进：
1. 默认留空=0时，按10万次(10^5=100000)大约相当于16.5层的组合
2. 输入>0 的正整数时，按输入值作为递归计算深度
   (该数值可大可小，小了速度快但可能漏掉很多组合解……大了速度降低)
3. 输入<0的负数如=-1时，不限制递归计算深度……每次都是计算直到有解了或者达到剪枝条件时才清零退出

香川群子

彭版出的题目的帖子
http://club.excelhome.net/forum. ... p;page=7#pid6353576

有兴趣的可以从头慢慢看，其中很多人的回帖也很有技术含量。

没兴趣的就看我的附件，计算1-100求总和=100的组合解，耗时不到1秒（机器好的话大约0.3秒）

而一般人中间最快的算法，也会要3-7秒。

香川群子

2楼的附件只能用来计算1-n的连续自然数、目标和值可以任意。

所以这个程序速度虽然最快，但并不具有通用性、实用性。

但它为递归算法的高效算法，奠定了基础。

香川群子

sheet2中有三个论坛里较难解决的求助帖，作为案例。

用通常的方法是难以得到解答，但用我的程序适当调整参数以后就能很快得到组合解的答案了。


建议今后有凑数、凑金额要求的，都请推荐来用我的程序，用法不太明白的可以直接来问我。
不要再说什么规划求解的话了……规划求解是没有用的。

香川群子

其实，原始数据中如果还含有负数，那么计算量的增加会非常厉害！

但是应用我的程序算法，却仍然能处理。

香川群子

我的递归程序在实用化上面，有一项重大发明：【单次递归计算深度】参数的应用。

如果源数据分布较均匀，满足条件的组合解有很多，
那么递归过程会很顺利，每向下深入递归1次到2次，就可能发现一个有效解……（自然数序列时）

但实际情形显然不可能如此，因此，递归会以近似剩余个数n的2^n的级别进行深度递归计算，
直到有解或最后仍然无解……

我发现，大部分情况下，如果一开始没有解，那么后面有解的概率会很低、很低。
因此，我设置了单次递归计算深度的限制条件，默认为计算10万次。（大约是向下搜索16-17层）
如果接下来连续16个数的全部组合都没有解，那么就不再向下搜索了。

这个方法，当然会漏掉一些解，但在提高通用性程序不死机的效果上，具有明显的好处。

因此，我的这项发明，是可以值得骄傲的。


sheet2中例子3：
http://club.excelhome.net/thread-386306-2-1.html
在以下29个数据求目标总和=404034.3，就是个很好的例子
975,1001,1398,5538,10345,12128,12133,13000,13000,13000,13000,13000,15068.6,15485.4,15700,15717.8,19680.5,20674.9,24880.5,25000,25256,29877.1,33992,34710.6,43500,50797.6,54540,64629.3


按默认递归计算深度=10万次时，计算1秒不到得到 6组解。
但是如果设置递归计算深度=50万次时，计算10秒能得到 33组解。

这已经是全部解了。因为即使设置递归计算深度到100万次，结果也是一样的。

注意到计算速度的差异为 10多倍。
如果设置计算深度为 35000时（实际能得到组合解的最小递归深度）
那么得到1组解，但耗时仅0.1秒。

如果不需要全部组合解，或者不需要很多解时，用这个方法来提高计算效率是很好的方法。

ps：
如果不设置计算深度，往往程序会在某个区间进入假死状态。
（当剩余计算量为2^n个组合，而这一分支的最后结果仍然是无解时）


本题举例中全部数据仅29个，如果原始数据个数增加到200个、300个时，
如果不有效进行递归深度的设置，那么计算一定会死机。

香川群子

程序在通用性、实用性方面做了很多改进，但是速度效率也就有较大的牺牲了。

以自然序列计算1-100求总和=100的全部组合解444793为例，
我的【仅能计算任意正整数】的递归剪枝算法，计算只需1秒（不含输出）。
含输出结果的也大约只需2秒不到，但现在的通用计算程序需要大约2.5秒以上。

但这些速度效率的牺牲是值得的。一个通用性强的程序才有实用价值。

香川群子

灰袍法师 发表于 2014-1-2 16:08
说得好，宁肯慢一点，反正计算的时候用户可以趁机偷懒。。。。。。

其实也只是稍微慢了一点，比起普通二进制组合算法，仍然是火车和牛车的差别。

最最关键是，适当的参数调整就可以不死机，一般在几十秒之内就有结果了。

香川群子

欢迎大家使用后发表感想……

另外，如果程序使用中有问题，可以随时提问咨询。

我在这里会礼貌地进行答复……但如果是私信就会粗俗地回复……呵呵。

香川群子

Ron2000 发表于 2014-1-3 10:07
支持香川大侠，看得出花很多时间整理、说明。加了参数配置，考虑了实际应用的很多情况！

组合计算以外，我的参数设置才是亮点。

一般人考虑不到那么细致的……女生的特长么、心细。