分支限界法 0-1背包问题-优先队列式

  1 #include<iostream>
  2 #include<queue>
  3 using namespace std;
  4 
  5 const int maxn=99; 
  6 int n,c;
  7 int w[maxn];
  8 int v[maxn];
  9 
 10 int bestv=0;
 11 int bestx[maxn];
 12 int total=1;        //解空间中的节点数累计，全局变量 
 13 struct nodetype        //队列中的结点类型
 14 {
 15     int no;            //结点编号，从1开始 
 16     int i;            //当前结点在搜索空间中的层次 
 17     int w;            //当前结点的总重量 
 18     int v;            //当前结点的总价值 
 19     int x[maxn];    //当前结点包含的解向量 
 20     double ub;        //上界 
 21     bool operator<(const nodetype &s)const //重载<关系函数
 22     {
 23         return ub<s.ub;   //ub越大越优先出队 
 24      } 
 25 };
 26 
 27 void input()
 28 {
 29     cout<<"请输入物品的个数："<<endl;
 30     cin>>n;
 31     cout<<"请输入每个物品的重量及价值(如5 4):"<<endl;
 32     for(int i = 1; i <= n; i++)
 33     {
 34         cin>>w[i]>>v[i];
 35     }
 36     cout<<"请输入背包的容量："<<endl;
 37     cin>>c;
 38 }
 39 
 40 void bound(nodetype &e)        //计算分支结点e的上界 
 41 {
 42     int i=e.i+1;        //考虑结点e的余下物品
 43     int sumw=e.w;
 44     double sumv=e.v;
 45     while((sumw+w[i]<=c)&&i<=n) 
 46     {
 47         sumw+=w[i];
 48         sumv+=v[i];
 49         i++;
 50     }
 51     if(i<=n)            //余下物品只能部分装入 
 52     e.ub=sumv+(c-sumw)*v[i]/w[i];
 53     else e.ub=sumv; 
 54 } 
 55 
 56 void enqueue(nodetype e,priority_queue<nodetype> &qu)
 57 //结点e进队qu 
 58 {
 59     if(e.i==n)                //到达叶子节点，不在扩展对应一个解 
 60     {
 61         if(e.v>bestv)        //找到更大价值的解 
 62         {
 63             bestv=e.v;
 64             for(int j=1;j<=n;j++)
 65             bestx[j]=e.x[j];
 66         }
 67     }
 68     else qu.push(e);        //非叶子结点进队
 69 } 
 70 
 71 void bfs()
 72 {
 73     int j;
 74     nodetype e,e1,e2;
 75     priority_queue<nodetype> qu;
 76     
 77     e.i=0;
 78     e.w=0;
 79     e.v=0;
 80     e.no=total++;
 81     
 82     for(j=1;j<=n;j++)
 83     e.x[j]=0;
 84     bound(e);
 85     qu.push(e);
 86     
 87     while(!qu.empty())
 88     {
 89         e=qu.top();qu.pop();    //出队结点e 
 90         if(e.w+w[e.i+1]<=c)        //剪枝，检查左孩子结点 
 91         {
 92             e1.no=total++;        //建立左孩子结点 
 93             e1.i=e.i+1;
 94             e1.w=e.w+w[e1.i];
 95             e1.v=e.v+v[e1.i];
 96             for(j=1;j<=n;j++)
 97             e1.x[j]=e.x[j];
 98             e1.x[e1.i]=1;
 99             bound(e1);        //求左孩子的上界 
100             enqueue(e1,qu);    //左孩子结点进队 
101         }
102         e2.no=total++;
103         e2.i=e.i+1;
104         e2.w=e.w;
105         e2.v=e.v; 
106         for(j=1;j<=n;j++)
107             e2.x[j]=e.x[j];
108         e2.x[e2.i]=0;
109         bound(e2);
110         if(e2.ub>bestv)        //若右孩子结点可行，则进队，否则被剪枝 
111         enqueue(e2,qu);    
112     }
113 } 
114 
115 void output()
116 {
117     cout<<"最优值是:"<<bestv<<endl;
118     cout<<"(";
119     for(int i=1;i<=n;i++)
120         cout<<bestx[i]<<" ";
121     cout<<")";
122 }
123 
124 int main()
125 {
126     input();
127     bfs();
128     output();
129     return 0;
130  }