赞
踩
在写代码的过程中参考了下面这篇博主的博客:背包问题
直接上代码,都有完整的注释的,喜欢就好:
//分支限界法 #include<iostream> #include<algorithm> #include<cstdio> #include<queue> const int MAX_N = 22; using namespace std; int n; // 表示有n个物品 int weights=16; //表示背包完整重量 int bound=0; //表示已有最优解 struct wu //记录物品 { int i; //表示原来物品的索引 int weight; //记录物品的重量 int value; //记录物品的价值 int sale ; //记录物品的价值/重量 }; struct Node { wu w; //记录该节点选择的物品 bool visited[MAX_N];//标记哪些点走了 bool notvisited[MAX_N];//标记哪些点不选择走 bool nochose[MAX_N]; //当前尚待选择的商品集合 int k; //已经选择的物品数 int ub; //目标函数的值(目标结果) bool operator <(const Node &p)const { return p.ub > ub;//目标函数值小的先出队列 } }; priority_queue<Node> pq;//创建一个优先队列 void sort(wu *w) //冒泡排序 { for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(w[i].sale < w[j].sale) { wu temp = w[i]; w[i] = w[j]; w[j] = temp; } } } } //得到上界值 int get_ub(Node p,wu *w) { int k = weights; int value=0; for(int i=0;i<n;i++)//背包剩余重量 { if(p.visited[i] == true) { k-=w[i].weight; value+=w[i].value; } } //找到最大的价值比,排除已经被选择的 cout<<"w:"<<weights-k<<" v:"<<value<<endl; for(int i=0;i<n;i++) { if(p.nochose[i] == true) //找到的第一个就是最大价值比 { cout<<"ub="<<value+k*w[i].sale<<endl; return value+k*w[i].sale; } } return value; } //判断nochose是否全为false即bound是否应该更新 bool isF(bool *nochose) { for(int i=0;i<n;i++) { if(nochose[i]==true) { return false; } } return true; } int get_w(Node p,wu *w) { int k =0; for(int i=0;i<n;i++)//背包剩余重量 { if(p.visited[i] == true) { k+=w[i].weight; } } return k; } void slove(wu *w) { //step2 Node p; p.ub = 0; //step2 -2 初始化 for(int i=0;i<n;i++) p.visited[i]=false; for(int i=0;i<n;i++) p.notvisited[i]=false; for(int i=0;i<n;i++) p.nochose[i]=true; p.k = 0; //step3 while(p.k!=n) { //step4: 分支一,包含该节点 Node Y; //判断包含该节点是否超重 if(get_w(p,w)+w[p.k].weight<=weights) { cout<<"包含物品:"<<w[p.k].i<<endl; for(int i=0;i<n;i++) Y.visited[i]=p.visited[i]; Y.visited[p.k] = true; for(int i=0;i<n;i++) Y.notvisited[i]=p.notvisited[i]; for(int i=0;i<n;i++) Y.nochose[i]=p.nochose[i]; Y.nochose[p.k] = false; Y.k = p.k+1; //判断是否加入队列 Y.ub =get_ub(Y,w); if(Y.ub > bound) pq.push(Y); //判断nochose是否全为false即bound是否应该更新 if(isF(Y.nochose)==true) { cout<<"这是一个可行解:"<<Y.ub<<endl; if(bound<Y.ub) { bound = Y.ub; } else{ cout<<"但是不如已有最优解好,减枝"<<endl; } } } else { cout<<"包含物品"<<w[p.k].i<<"不可行"<<endl; } //step4(5): 分支二,不包含该节点 Node Z; cout<<"不包含物品:"<<w[p.k].i<<endl; for(int i=0;i<n;i++) Z.visited[i]=p.visited[i]; for(int i=0;i<n;i++) Z.notvisited[i]=p.notvisited[i]; Z.notvisited[p.k] = true; for(int i=0;i<n;i++) Z.nochose[i]=p.nochose[i]; Z.nochose[p.k] = false; Z.k = p.k+1; //判断是否加入队列 Z.ub = get_ub(Z,w); if(Z.ub > bound) pq.push(Z); if(isF(Z.nochose)==true) { cout<<"这是一个可行解:"<<Z.ub<<endl; if(bound<Z.ub) { bound = Z.ub; } else{ cout<<"但是不如已有最优解好,减枝"<<endl; } } p=pq.top(); pq.pop(); } cout<<bound <<endl; //step3 //输出选择的物品 cout<<"选择的物品为"<<endl; for(int i=0;i<n;i++) { if(p.visited[i] == true) { cout<<w[i].i<<"\t"; } } } int main() { cout<<"请输入物品的数量:"<<endl; cin>>n; //输入物品的数量 cout<<"请输入背包的承重量:"<<endl; cin>>weights; cout<<"请输入每一个物品的重量和价值:"<<endl; wu *w = new wu[n]; for(int i=0;i<n;i++) { w[i].i = i; cin>>w[i].weight; cin>>w[i].value; w[i].sale = w[i].value/w[i].weight; } //step1 bound = 0; sort(w); slove(w); } /* 实例 请输入物品的数量: 4 请输入背包的承重量: 10 请输入每一个物品的重量和价值: 4 40 7 42 5 25 3 12 */
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。