【讨论】【回帖有分】最优组合算法问题！
属性1属性2属性3
A1001015
B2002035
C500515
D1000323
E300731
F500318
A、B、C、D、E、F....代表物品名称
属性1、2、3分别代表每个物品的一种属性
现在给定一个要求：从这些物品中取出一定数量的物品，要求它们属性1的总和小于X，属性2的总和小于Y，但是要保证属性3的总和是最大，应该如何取？将最优的结果列举出来，如果有多条最优可以分多条列举。
注：同一个物品可以取多个。
我这个只是一个例子，里面只随便列举了6个物品，实际情况下有300多个物品，希望能得到一个比较快点的算法。
大家踊跃讨论，回帖有分！
解决问题的重新开贴给分！
[解决办法]
占个位置，坐下慢慢看。
[解决办法]
从这些里取出一定数量n个物品
把属性1,属性2,属性3的数据分别放到3个TStringList里
对属性3的StringList用Sort()方法排序,从最后一个(也就是最大的那个)开始循环去n个,同时计算对应的X和Y 如果X,Y同时符合要求那取出这n个数据 如果不符合那继续在属性3的StringList里往上寻找n个
只是解决这个问题,没有考虑效率,慢慢想
[解决办法]
呵呵,我就看看不说话
[解决办法]
这要用到线性代数、矩阵运算。
[解决办法]
有点难度，得一定时间思考！！
[解决办法]
遗传算法解决吧，寻优问题，不是最值问题
[解决办法]
假设要取的个数为N=3, 属性1的总和小于X=1000, 属性2的总和小于Y=100
属性1 属性2 属性3
A 100 10 15
B 200 20 35
C 500 5 15
D 1000 3 23
E 300 7 31
F 500 3 18
首先把上述数据按照属性3倒排序(这个可以放到数据库里去处理,也可以用常用的排序算法去处理)
处理结果如下
属性1 属性2 属性3
200 20 35
300 7 31
1000 3 23
500 3 18
100 10 15
500 5 15
对上述排序好的数据扩展,这个处理主要是考虑到每个物品可以重复,扩展的规则如下
1.每个物品重复的次数为0~N次
2.每次重复后属性2的和不能超过X,属性3的合不能超过Y
根据规则上述数据变成如下数据
200 20 35
200 20 35
200 20 35
200 20 35 //这笔重复4次
300 7 31
300 7 31
300 7 31 //这笔重复3次
500 3 18 //这笔不重复,超过Y或X的直接不考虑
100 10 15
100 10 15
100 10 15
100 10 15
100 10 15
100 10 15
100 10 15
100 10 15
100 10 15 //这笔重复9次
500 5 15 //这笔不重复
然后循环上面的数据,每次取N组 直到 X的合计和Y的合计符合条件
[解决办法]
学习。。。
[解决办法]
先看看
[解决办法]
等我先看看离散数学
[解决办法]
听复杂，我感觉应该用运筹学的方法解决
[解决办法]
[解决办法]
日 还没想出来 挺难弄的 等高手出现
[解决办法]
运筹学的理论很容易解决吧。
找个学数学的，建个模，
就不难解决了，
无非是解方程。
[解决办法]
算法复杂，容易死脑细胞
[解决办法]
太难了...
[解决办法]
对我来说很难
[解决办法]
本质就是一个搜索问题。
最简单的方法就是回溯，枚举出所有的情况，找出符合条件的就行。
[解决办法]
注：同一个物品可以取多个。
我理解没有到位。
好难！
[解决办法]
典型的背包问题嘛。帖子记住了，星期一回来帮你写代码。
[解决办法]
期待楼上的代码早日出现
[解决办法]
待楼上的代码早日出现
[解决办法]
穷举法
[解决办法]
我怎么看不明白题意啊，属性3最大的都比属性1最小的小，那怎么可能让“属性3的总和最大”呢？
[解决办法]
数学问题了
[解决办法]
看着怎么想01背包问题啊
[解决办法]
错了 没看见一个物品可以取多个 不能用背包的解法
[解决办法]
典型的线性规划问题！用300种物品举例。用lingo求解：
model:
!定义一个物品集，他的属性有x:该物品是否被使用。y：如果使用该物品，该使用多少件。a，b，c分别是三个属性。；
！X，Y为常数；
sets:
goods/goods1..goods300/:x,y,a,b,c;
endsets
@for(goods:@bin(x);@gin(y)）；
@sum(goods(i):x(i)*y(i)*a(i))<X;
@sum(goods(i):x(i)*y(i)*b(i))<Y;
max=@sum(goods(i):x(i)*y(i)*c(*));
data:
a,b,c=100 10 15
200 20 35
500 5 15
1000 3 23
300 7 31
500 3 18
!由于没有给出300种物品的属性，在这里只列举6种，必须加到300种；
enddata
end
[解决办法]
典型的线性规划,搜索一下:单纯形法,并不复杂
[解决办法]
回帖是一种美德！
[解决办法]
顶了在看。
[解决办法]
先更正一下
max=@sum(goods(i):x(i)*y(i)*c(i));
我用的是lingo语言，lingo是专门处理规划问题的工具。当然采用的是分支定界法和单纯型法。
用lingo处理最好。
[解决办法]
有点难度，好好学习一下
[解决办法]
thinking...
[解决办法]
可以用迭代法，可能不是最优的，但保证可以找到正确结果，伪代码：
- C/C++ code
// 用堆栈stack来保存物品的组合bool IsOK（const stack& ); //判断 属性1之和<X and 属性2之和<Y travel(stack &s){ for(int i=0; i<300; i++) { s.push(obj[i]); //加入第i件物品 if(IsOK(s)) // 如果条件符合 { setMaxCond(s); // 如果s里的属性3之和最大，就记录之 travel(s); // 递归，断续加入更多物品 } s.pop(); //测试完成后取出前面加入的第i件物品（换下一件） }}
------解决方案--------------------
[解决办法]
属于组合数学的范畴吧
[解决办法]
hao wen ti
[解决办法]
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS
[解决办法]
mark先
[解决办法]
修改一下原来的伪代码，使用组合方式
- C/C++ code
travel(stack &s, int start){ for(int i=start; i<300; i++) { s.push(obj[i]); //加入第i件物品 if(IsOK(s)) // 如果条件符合 { travel(s, i); // 递归，断续加入更多物品 } else //只有叠加到极限时才比较记录（前提是属性３没有负数） { s.pop(); setMaxCond(s); // 如果s里的属性3之和最大，就记录之 } s.pop(); }}
[解决办法]
看了一下你的代码，IsOK可以改进一下
if(sumX > X || sumY > Y)
return false;
最好放到for的外面。
另外，传list的同时可以再传一个当前list的sumX和sumY，加入/减去一个物品时更新一下list的sumX和sumY(只要一次加/减运算即可)，免去的每次都从用for从头加到尾，浪费时间。
[解决办法]
[解决办法]
我的代码：
- C/C++ code
#include <iostream>#include <string>#include <vector>#include <iterator>using namespace std;struct TObj{ char name; int prop1; int prop2; int prop3;};struct TGroup{ vector<int> vecObj; // 物品组合（索引） int nX; // 属性1剩余点数 int nY; // 属性2剩余点数 int nSumZ; // 属性3总和};// 参数：物品数组objlist、物品数组大小n，临时组合grp，新加物品的起始索引i，属性3的最大组合maxgrpvoid travel(const TObj *objlist, const int n, TGroup &grp, int i, TGroup &maxgrp){ //下面两行输出所有组合，确认是否有重复组合出现 //copy(grp.vecObj.begin(), grp.vecObj.end(), ostream_iterator<int>(cout)); //cout << "\t nX: " << grp.nX << ";nY " << grp.nY << ";nSumZ: " << grp.nSumZ << endl; for(; i<n; ++i) { const TObj & obj = objlist[i]; if(grp.nX >= obj.prop1 && grp.nY >= obj.prop2)// 剩余点数足够 { // 加入当前物品索引 grp.vecObj.push_back(i); grp.nX -= obj.prop1; grp.nY -= obj.prop2; grp.nSumZ += obj.prop3; // 抽取最大组合 if(maxgrp.nSumZ < grp.nSumZ) maxgrp = grp; // 继续尝试 travel(objlist, n, grp, i, maxgrp); // 恢复 grp.vecObj.pop_back(); grp.nX += obj.prop1; grp.nY += obj.prop2; grp.nSumZ -= obj.prop3; } }}TObj g_objs[6]={ {'A',100,10,10}, {'B',200,21,21}, {'C',300,33,35}, {'D',400,42,48}, {'E',500,56,60}, {'F',600,65,81}};int main(int argc, char* argv[]){ // 临时组合初始值 TGroup grp; grp.nX = 10000; grp.nY = 1000; grp.nSumZ = 0; // 最大组合 TGroup maxgrp=grp; travel(g_objs, 6, grp, 0, maxgrp); // 输出结果 for(vector<int>::const_iterator itr=maxgrp.vecObj.begin(); itr!=maxgrp.vecObj.end(); ++itr) { cout << g_objs[*itr].name << ' '; } cout << endl << "属性1总和:" << 10000 - maxgrp.nX << endl; cout << "属性2总和:" << 1000 - maxgrp.nY << endl; cout << "属性3总和:" << maxgrp.nSumZ << endl; // 暂停 cin.get(); return 0;}
[解决办法]
[解决办法]
毛毛的代码也有点问题，当X，Y一样时会出现负数
[解决办法]
～有一个不准确但速度很快的办法如果数量在10000+可以考虑
把属性三分别除以属性一，属性二之后用加权平均（根据xy的限制的倒数）算出一个值
按照这个值列表
从大到小依次排
在没达到xy的情况下从大到小依次添加遇到超过xy限制的跳过看下一个直到遍历
还可以做别的优化比如根据遍历后剩余的空间（xy）再更换物品
好吧其实我什么都不懂...咱是来打酱油