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

iNicol

香川群子 发表于 2017-6-1 20:31
一共会有444,793组解。全部输出没意义了。

哦,原来是这样。本来就没显示完。感谢！

ishigang

香川群子 发表于 2014-3-31 00:38
这个当然也可以做到，但得到的结果就会是所有有解组合中的不重复组合……

那么，如果你没有一个明确的 ...

老师您好，我看了这个帖子里您所有的回复，我的问题与您41楼提到的一样

我有一些数值，需要从中提取出所有能组合成1000的值（或者目标值是一个范围，例如900~1000），每个值使用过一次之后就不能再使用（不重复使用），我遇到的这个问题是只要能凑出目标值就可以，不管是由多少个数值凑出来的都没有限制，但是需要拼凑的数值会有很多的重复。（“随便取出一些组合直到剩余最后几个无法组合成就算结束”）

我看过您后面给出的一个附件，里面有零件、长度等等，感觉不如一楼的程序看起来简洁，像我这种问题，能写出代码来吗？

比如下面这边数据，假设我要提取目标值是1000的组合，每个数据使用一次后就不再重复使用，能不能帮忙解决一下呀，谢谢啦。

数值：

985
972
970
970
960
960
950
891
880
850
850
801
792
770
750
740
740
730
700
699
680
670
660
650
650
650
650
650
650
600
590
570
560
550
550
500
500
500
490
470
450
450
450
450
440
380
350
200
200
50
44
30
20

香川群子

ishigang 发表于 2017-7-23 01:41
老师您好，我看了这个帖子里您所有的回复，我的问题与您41楼提到的一样

我有一些数值，需要从中提取出 ...

很多凑不起来。只能做到这样子：

1000	1*450+1*550
1000	2*500
1000	1*440+1*560
1000	1*50+1*350+1*600
1000	1*20+1*30+1*950
994	1*44+1*450+1*500
992	1*200+1*792
985	1*985
972	1*972
970	1*970
970	1*380+1*590
970	1*200+1*770
960	1*960
960	1*470+1*490
891	1*891
880	1*880
850	1*850
801	1*801
750	1*750
740	1*740
730	1*730
700	1*700
699	1*699
680	1*680
670	1*670
660	1*660
650	1*650
570	1*570
450	1*450

香川群子

需要使用另一种程序。类似于一维下料计算。

ishigang

香川群子 发表于 2017-7-23 11:34
需要使用另一种程序。类似于一维下料计算。

老师说的对，其实我就是在算下料，铺地板（或者可以理解成铺地砖），整块的材料数出总块数就可以了，最后剩下一些收口的不能使用整块材料的地方，我算出来应该切割成的长和宽，然后把这些切割的材料的边长组合拼凑，哪些数值可以拼出一个整块就把哪些数值归纳为一块材料（其实每块材料我只能取一个边长来拼凑，需要忽略另一条边长，比如整块材料边长是1000*1000，切割的材料有1000*800、10000*500，还有900*800、600*500，像两条边长都需要切割的，我只能取其中一个边长使用，我还做不到把两条边长都小于1000的材料百分之百的进行优化下料。

像我需要的这种凑数字，最终肯定会剩下一些不能组合的几组数字，剩下的数字最后只能由人主观去进行拼凑了。

实现上面的要求，就是想进行优化下料。地材铺装，而且是做工程，我现在还没找到有什么好的优化下料软件

您看我这个问题能解决么，谢谢了。

ishigang

香川群子 发表于 2017-7-23 11:32
很多凑不起来。只能做到这样子：

您这个是给的提取某一个范围内的凑数，其实这样也能解决一大部分问题了，最终还会剩下一些凑不起来的数值是正常的

ishigang

香川群子 发表于 2017-7-23 11:34
需要使用另一种程序。类似于一维下料计算。

我发个附件，您看一下我的整理过程吧

附件表格里一共三个工作表，从后向前依次是“原始统计数据”、“数据整理过程”、“凑数结果”

最终就是实现优化下料，您看看有没有兴趣研究一下呀

谢谢老师

我的浏览器有问题，附件上传了两次，两个附件是一样的

suxianchun1

hi  剪枝算法是根据金额排序后 得出结果 ， 我现在有个需求是要按照日期排序，根据日期在前的金额优先取出组合数和制定金额接近的算法。请问怎么处理

suxianchun1

香川群子 发表于 2017-7-23 11:34
需要使用另一种程序。类似于一维下料计算。

老师您好  剪枝算法是根据金额排序后 得出结果 ， 我现在有个需求是要按照日期排序，根据日期在前的金额优先取出组合数和制定金额接近的算法。请问怎么处理

xiangyun@

太强大了..