采用队列式分枝限界法求解0/1背包问题的算法#include #include using namespace std;#define MAXN 20//最多可能物品数#define INF 0x3f3f3f3f3//定义∞//问题表示int n=3,W=30;int w[]={0,16,15,15};//重量，下标0不用int v[]={0,45,25,25};//价值，下标0不用//求解结果表示int maxv=-9999;//存放最大价值,全局变量int bestx[MAXN];//存放最优解,全局变量int total=1;//解空间中结点数累计,全局变量struct NodeType//队列中的结点类型{ int no;//结点编号 int i;//当前结点在搜索空间中的层次 int w;//当前结点的总重量 int v;//当前结点的总价值 int x[MAXN];//当前结点包含的解向量 double ub;//上界 bool operator<(const NodeType &s) const //重载<关系函数 {return ub &qu) //结点e进队qu{ if (e.i==n)//到达叶子结点 {if (e.v>maxv)//找到更大价值的解{maxv=e.v;for (int j=1;j<=n;j++)bestx[j]=e.x[j];} } else qu.push(e); }void bfs()//求0/1背包的最优解{ int j; NodeType e,e1,e2;//定义3个结点 priority_queue qu;//定义一个队列 e.i=0;//根结点置初值，其层次计为0 e.w=0; e.v=0; e.no=total++; for (j=1;j<=n;j++)e.x[j]=0; bound(e);//求根结点的上界 qu.push(e);//根结点进队 while (!qu.empty())//队不空循环 {e=qu.top(); qu.pop();//出队结点eif ()//剪枝：检查左孩子结点{e1.no=total++; e1.i=e.i+1;//建立左孩子结点e1.w=e.w+w[e1.i];e1.v=e.v+v[e1.i];for (j=1;j<=n;j++)//复制解向量e1.x[j]=e.x[j];e1.x[e1.i]=1;bound(e1);//求左孩子结点的上界EnQueue(e1,qu);//左孩子结点进队操作}e2.no=total++;//建立右孩子结点e2.i=e.i+1;e2.w=e.w; e2.v=e.v;for (j=1;j<=n;j++)//复制解向量e2.x[j]=e.x[j];e2.x[e2.i]=0;bound(e2);//求右孩子结点的上界if ()//若右孩子结点可行,则进队,否则被剪枝EnQueue(e2,qu); }}