一堆数字凑金额(凑数值) - 一个求解子集和问题的高速算法(有条件限制)

灰袍法师

这个算法跟数据行数没关系的，只跟数值大小有关，你的数值又不大，在我的电脑算没问题啊

估计是你的Excel安装有问题吧，有宏病毒或者是绿色版？？？

同时打开的excel文档太多？？？

试一下按Alt_F11，工具－选项－通用，查看错误捕获的设置是什么
改为 遇到未处理的错误时中断。
还不行，就在
If max_record < 100000 Then max_record = 100000
这一行下面增加 if max_record > 1000000 then max_record = max_record * 0.45
试一下

下面是答案
第一个数值 367919.3 的组合是
17910.44
207946.37
10513.90
12754.80
4892.06
1358.30
3171.37
2999.18
106372.88
剩下的数字可以有以下组合得到 847075
229180.41
19429.84
368550.04
195006.69
15949.74
1500.76
786.97
108.00
2589.13
4387.16
36.00
9550.26

附图：

從零開始27

为何这种方式不能出现多个组合的呢？？就好比：1-10，计算15的话，怎么样才能显示出全部的方法，而不是只有一种？

灰袍法师

從零開始27 发表于 2012-9-10 16:59
为何这种方式不能出现多个组合的呢？？就好比：1-10，计算15的话，怎么样才能显示出全部的方法，而不是只有 ...

显示全部的组合是没有任何实际意义的
所以。。。。。。

awaw0913

法师~

我下了你的附件，把数字输入到B列，选了最大值和最小值，可是算不出我要的结果，应该怎么弄呢？

我是有一组数字，和一个固定数字，要从中找出一些数字的和等于这个固定数字~

shminy

非常好，感谢。。

可宜

能不能不用VBA呢？

lee1892

个人觉得具有更为广泛用途的是生产排料，如下两种
1、原材料定长，求得下料组合，使得材料利用率最大
2、原材料连续，加工顺序分两步，先下定长材料，再按尺寸下料，求得下料组合，使得定长材料种类尽可能少，同时使得材料利用率最大。通常是个平衡关系，而没有最优解。

而更为复杂的则是板材的使用。。。

法师有啥指导意见不。。。
==============
找了本NP的书，俺先看看。。。

灰袍法师

lee1892 发表于 2012-11-29 10:50
个人觉得具有更为广泛用途的是生产排料，如下两种
1、原材料定长，求得下料组合，使得材料利用率最大
2、 ...

参考这个帖
http://club.excelhome.net/thread-920256-1-1.html
楼层很高，你最好看完在下载，之前楼层的附件也就是提供测试数据的作用而已。
我贴上了两种算法的VBA解决方案 在71楼和75楼，以及一本某个国产软件开发者的使用手册（有点参考价值）

你说的两个问题，我在实际计算中发现其实“几乎”是一个问题
利用率高的方案，往往使用的原材料开料也少
对存在 利用率高 vs 开料方案少 的选择，其实只需要改变一下 最优估值函数，就可以计算出 最高利用率 或者 最低开料方案数

我的方法是 基于本帖的代码 生成可行组合，然后随机采用这些可行组合，用估值函数来选最好的一个
最后发现效果非常好，比一些商业软件都要好！
板材的话，我没做过，市场上卖的同类软件也不少，自己搞没啥意思。
麻烦之余，即使做出更好的结果，老板也不会多谢你半句。

灰袍法师

hiwrw 发表于 2013-1-10 20:49
我的数据在以上压缩包中，我将原表中的数据更换成我的数据后，经过操作，出不来明细，不知何原因，请高人指 ...

是因为数值太大，内存溢出了。把最大的那个正数和最大的负数都删掉就可以了。
其中一个结果是：
+790000 +500000 +206739.16 +154613.2 +83569.01 +73373.33 +69852.07 +54871.42 +48500.05 +39102.1 +28117.7 +19344.16 =  2068082.20
当然，你也可以用我顶楼给出的链接，里面香川群子的程序
计算这样的大数值会比我的这个程序要好。
唯一麻烦之处是，她那个程序需要先人手把所有数值x100变成整数才能计算。

hiwrw

我的数据在此压缩包中