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

航起帆扬

谢楼主，学习。

gjj136138139

很不错！这是2014年最好的礼物了，谢谢楼主。

香川群子

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

如果源数据分布较均匀，满足条件的组合解有很多，
那么递归过程会很顺利，每向下深入递归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秒以上。

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

sportskill

学习一下，谢谢分享！

高文贤

{:soso_e179:}

灰袍法师

香川群子 发表于 2014-1-2 10:28
程序在通用性、实用性方面做了很多改进，但是速度效率也就有较大的牺牲了。

以自然序列计算1-100求总和= ...

说得好，宁肯慢一点，反正计算的时候用户可以趁机偷懒。。。。。。

m_n_j001

香帅就是帅！美女就是美！

no11road

学习一下，谢谢香川老师

huangyun

收藏了，下次凑数字可有大用长了。