分支限界法装载问题

分支限界

#include #include #include #include using namespace std; ifstream infile; ofstream outfile; class Node { friend int func(int*, int, int, int*); public: int ID; double weight;//物品的重量 }; bool comp1(Node a, Node b) //定义比较规则 { return a.weight > b.weight; } class Load; class bbnode; class Current { friend Load; friend struct Comp2; private: int upweight;//重量上界 int weight;//结点相应的重量 int level;//活结点在子集树中所处的层次 bbnode* ptr;//指向活结点在子集树中相应结点的指针 }; struct Comp2 { bool operator () (Current *x, Current *y) { return x->upweightupweight; } }; class Load { friend int func(int*, int, int, int*); public: int Max0(); private: priority_queue, Comp2>H;//利用优先队列（最大堆）储存 int limit(int i); void AddLiveNode(int up, int cw, bool ch, int level); bbnode *P;//指向扩展结点的指针 int c;//背包的容量 int n;//物品的数目 int *w;//重量数组 int cw;//当前装载量 int *bestx;//最优解方案数组 }; class bbnode { friend Load; friend int func( int*, int, int, int*); bbnode* parent; bool lchild; }; //结点中有双亲指针以及左儿子标志 int Load::limit(int i) //计算结点所相应重量的上界 { int left,a; left= c - cw;//剩余容量 a = cw; //b是重量上界，初始值为已经得到的重量 while (i <= n && w[i] <= left) { left -= w[i]; a += w[i]; i++; } return a; } void Load::AddLiveNode(int up, int cw, bool ch, int level) //将一个新的活结点插入到子集树和优先队列中 { bbnode *b = new bbnode; b->parent = P; b->lchild = ch; Current* N = new Current; N->upweight = up; N->weight = cw; N->level = level; N->ptr = b; H.push(N); } int Load::Max0() { int i = 1; P = 0; cw = 0; int bestw = 0; int up = limit(1); while (i != n + 1) { int wt = cw + w[i]; //检查当前扩展结点的左儿子结点 if (wt <= c)//左儿子结点是可行结点 { if (wt > bestw) bestw =wt; AddLiveNode(up,wt, true, i + 1); } up = limit(i + 1); //检查当前扩展结点的右儿子结点 if (up >= bestw)//如果右儿子可行 { AddLiveNode(up,cw, false, i + 1); } Current* N = H.top(); //取队头元素 H.pop(); P = N->ptr; cw = N->weight; up = N->upweight; i = N->level; } bestx = new int[n + 1]; for (int j = n; j > 0; --j) { bestx[j] = P->lchild; P = P->parent; } return cw; } int func(int *w, int c, int n, int *bestx) //调用Max0函数对子集树的优先队列式进行分支限界搜索 { int W = 0; //初始化装载的总质量为0 Node* Q = new Node[n]; for (int i = 0; i < n; ++i) { Q[i].ID = i + 1; Q[i].weight = w[i+1]; W += w[i+1]; } if (W <= c)//如果足够装，全部装入 return W; sort(Q, Q + n, comp1); //首先，将各物品按照重量从大到小进行排序； Load K; K.w = new int[n + 1]; for (int j = 0; j < n; j++) K.w[j + 1] = w[Q[j].ID]; K.cw = 0; K.c = c; K.n = n; int bestp = K.Max0(); for (int k = 0; k < n; k++) { bestx[Q[k].ID] = K.bestx[k + 1]; } delete []Q; delete []K.w; delete []K.bestx; return bestp; } int main() { int*w,*Final; int c,n,i,best; infile.open("input.txt",ios::in); if(!infile) { cerr<<"open error"<>c; infile>>n; w=new int[n+1]; for(i=1;i<=n;i++) infile>>w[i]; infile.close(); Final = new int[n+1]; best = func( w, c, n, Final); outfile.open("output.txt",ios::out); if(!outfile) { cerr<<"open error"<

文件下载

评论信息

其他资源

免责申明

【只为小站】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【只为小站】无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论【只为小站】经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见版权及免责申明

分支限界法 装载问题

文件下载

评论信息

其他资源

免责申明

个人信息

相关资源标签

热门下载

最新下载

分支限界法装载问题