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

吴立军123

香川群子 发表于 2019-7-23 07:31
搜索利用背包算法解决分组凑数

香川老师，我几年前用你的凑数组合程序基本上已经解决，多年来很是佩服你，你的帖子我不知道翻看多少遍了。只是有些小问题想直接问一下，更想当面表达感谢。很希望能加你Q，也请你给个机会。

吴立军123

吴立军123 发表于 2019-7-23 10:49
香川老师，我几年前用你的凑数组合程序基本上已经解决，多年来很是佩服你，你的帖子我不知道翻看多少遍了 ...

香川老师，还请百忙中私聊一下。

榨菜超

大神您好 我先前从论坛里下载了您的凑数字最佳递归程序 我有8组数据需要凑到接近目标值 4组可以 4组出来的结果是0 您如果方便的话能帮我看看么  第一组数据是：  586,848.60   1,578,580.50   1,784,621.80   8,836,534.50   1,625,598.90   1,625,102.30   4,246,432.50   10,000,000.00   10,000,000.00   1,581,848.50   10,000,000.00   10,000,000.00   10,000,000.00   3,134,665.70  需要的目标值是 51,335,844.30  第二组是 10,000,000.00   2,051,657.00   10,000,000.00   10,000,000.00   10,000,000.00   10,000,000.00   10,000,000.00   10,000,000.00   10,000,000.00   1,972,698.00   1,126,004.00   985,797.00   275,786.00   489,710.00   1,000,000.00   671,852.00   41,067.00   65,466.00   5,652,597.00  需要的目标值是 47,979,220.00  第三组是  1,294,106.10   10,000,000.00   10,000,000.00   456,092.40   470,365.50   212,373.50   719,109.50   738,672.30   4,702,669.60   2,610,590.30   1,628,526.20   4,187,878.60   4,466,766.10   4,509,860.40   3,689,265.00   8,106,525.50   2,751,705.00   100,000.00   100,000.00   100,000.00   75,487.52  需要的目标值是 36,569,005.20

秦始皇

老师，您好，请问您的帖子是否有这种算法：
一组固定的数据，但里面会有重复的数据。要挑一部分加总为特定的总金额。

汀渚草木树何处

老师 没得凑多个数字的例子吗，并且凑数的数据每个只能用一次？

mjx1122

@香川群子楼主用来凑正数好像没问题。附件里的好像用这个程序没法实现呢。
需求：
一列数据，有正有负有重复，一般不会超过200个数，凑数目标值，可能包含重复或负值组成。
可以实现吗？

lvmeirong1988

香川老师,我真的太仰慕你了，不知道大侠能不能解决我多年的心病。这个凑数加一个条件的VBA搜了全网都找不到。

您做的最佳递归剪枝算法计算组合求和是随机的，请问能在您原来的凑数基础上增加一个条件吗？

不知道能不能加一列条件，例如我们收到苏州大学一笔钱，但是苏州大学名下有187张发票，85个实验室，已知的实际情况是：每个实验室几乎不会混在一起打款，基本都是同一个实验室拿几张发票一起打款，如果能加一个实验室这个条件，那得出来的结果肯定非常准确了。

随机凑数就是会凑出很多种结果，而且这些结果都是多个实验室的发票金额凑在一起的，这不符合实际情况。

盼回复。。。

ilaoyao

非常感谢香川群子这个帖子。对我工作一个方面来说实用性简直是极强。虽然不能达到我要的那种程度，但是我适当加点参数来控制，现在简直就是利器。

谈一下我个人的使用感受和心得，或许能帮到同行：

我是一个施工企业的技术员，平时要用到材料配料这个活。一般可能是50~100组不同的尺寸，需要按照市场标准材料的长度来配料，譬如有60组数据，尺寸各不相同，资本家总是要最大限度的提高利用率，减少下料损耗，那么需要对这些数据进行整理，按照6米标准长度来配好下料单。这时候这个代码就起到非常大的作用。

但是我测试下来，这个代码好像是生成各种组合，就是60组数据中哪些数据在满足个数范围的情况下累加的和能够最大接近标准长度，更多的是排列出各个组合结果。但是跟配料上容易出现一个冲突就是，配料一旦一组数据参与了配料后，这组数据就不要剔除出下一轮的配料内。所以我增加了一些自己代码来控制，做一个调整：

1）设置程序每次只配一组数据的结果；
2）成功后将这组数据赋值为0.01或者更小，这样变通的就不让它们参与下一轮配料。
3）同时把这组数据读出到其他表格中并做好标记，表示已经配料过
4）自己设置一个for循环调用程序，一般我就也就也用到100次足够了，
5）每一次循环后就把上面的1~3操作一遍，这样到最后原始数据可能就剩下一组小于标准长度的数据。
基本上就能做到自动配料了。

也很支持与理解香川群子对代码的加密，所以我是采用这样的变通办法。
我只是提一个建议，能否在代码上设置显示出的结果是每个数据参与一次后的结果。这样就非常棒了！


我自己增加的代码中还有错误的情况未考虑周全，所以就放一个特定数据控制下的配料动图演示。







补充内容 (2019-11-13 21:27):
代码未加密，是我自己眼花看错了。

owencheung

今天没事看了下代码，香川群子对VBA太精通了。之前很繁琐的代码原来可以很简单的写出来。谢谢！

owencheung

ilaoyao 发表于 2019-11-9 21:33
非常感谢香川群子这个帖子。对我工作一个方面来说实用性简直是极强。虽然不能达到我要的那种程度，但是我适 ...

代码有加密码？没有吧。确实，大多实用的都是一个数只参加一次凑数，如果已参与凑数的能做上标记就好了。