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

mrdangdong

非常感谢楼主的分享！
我用100个不重复的6位数（3452.67依次加2）测试了一下，取前五个数字之和，录进去很快算出结果。
用后5个数字求和，录进去计算，一个小时后还在无响应状态...这还能有什么好办法呀？

香川群子

mrdangdong 发表于 2016-4-22 15:38
非常感谢楼主的分享！
我用100个不重复的6位数（3452.67依次加2）测试了一下，取前五个数字之和，录进去很 ...

如果已知是5个数之和，那么要输入个数n=5，然后计算。

如果计算最大5个数之和，只要几秒钟。

如果计算最小5个数之和，大约需要几十秒……递归计算深度要设置=-1

mrdangdong

香川群子 发表于 2016-4-22 23:08
如果已知是5个数之和，那么要输入个数n=5，然后计算。

如果计算最大5个数之和，只要几秒钟。

非常感谢，你的工具还是能解决一大部分人的需求的！
是我没有描述清楚，现实中一般是不知道n＝多少？，我拉了50个数据的和算了一下，溢出了。
我又分析了一下：A列基数越多，n越大，总的组合越大，基本无解，是不是可以这样说呢？

香川群子

mrdangdong 发表于 2016-4-25 09:44
非常感谢，你的工具还是能解决一大部分人的需求的！
是我没有描述清楚，现实中一般是不知道n＝多少？， ...

1、数据量越大，当然可能的组合越多，而且是2^n指数幂增大！
     这个基本上没有很好的办法，如果只需得到任意一组解，你可以随机去掉一半数据再计算。
     
    或者1个思路是：数据拆分为2组或更多k组，每一组要求凑满目标总和H的1/k附近，最后合并起来。


2、目标总和越大，当然可能的组合也会相应增加，尤其是小数值很多时。
    解决方法是，尽量去掉那些数值较小的部分。(需要适当保留一些)

3、不知道组合个数n时。
    你可以估计一个范围，进行初步筛选。比如10-15 根据计算结果改变或缩小或扩大n取值范围。

…………
总之，我的凑数程序已经是VBA中的经典了，足够用了。

zty3162258

踩一脚，留个印子

疯大爷

香川群子 发表于 2014-1-1 20:07
sheet2中有三个论坛里较难解决的求助帖，作为案例。

用通常的方法是难以得到解答，但用我的程序适当调整 ...

您好，看了您“实用凑数凑金额高效递归剪枝算法”这个帖子，实乃高人，不得不佩服。但我有个问题想问下，这个程序若是将求和变成就均值，该如何设定呢？问题即找出一组数中的以某个值为均值的各种组合。因为是经管类学生，对于变成这块未曾涉及，故而求助大神，忘解惑，拜谢！

香川群子

疯大爷 发表于 2016-5-10 09:14
您好，看了您“实用凑数凑金额高效递归剪枝算法”这个帖子，实乃高人，不得不佩服。但我有个问题想问下， ...

你需要确定取数n的范围，然后循环计算即可。

例如，
设n=10，计算总和=10*均值
继续设n=11，计算总和=11*均值
…………
直至结束。得到所有各种n分布的、满足均值条件的组合。

提醒，均值也可以设置范围，则总和范围=n*均值1 ~ n*均值2

疯大爷

香川群子 发表于 2016-5-10 12:44
你需要确定取数n的范围，然后循环计算即可。

例如，

好的，非常感谢，我去试试呢。

qhy3990

留言 待看  留言 待看  留言 待看