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

香川群子

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

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


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


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

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


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


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

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的连续自然数、目标和值可以任意。

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

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

windimi007

香川群子 发表于 2014-1-1 15:09
2楼的附件只能用来计算1-n的连续自然数、目标和值可以任意。

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

香川老师辛苦了，果断加分支持！

fffox

学习一下，谢谢香川老师

liucqa

你去找找法师来看看这个帖子，给个评价，俺好决定加不加分。因为俺看不懂

香川群子

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

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


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

香川群子

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

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

616891719

很厉害，值得学习{:soso_e179:}

青见

收藏慢慢学习，看是否能用到对账上。