分枝限界法求解01背包问题

2023年8月1日发(作者：)

分枝限界法求解01背包问题问题描述有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定⼀个容量为W的背包。设计从这些物品中选取⼀部分物品放⼊该背包的⽅案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，⽽且重量和为W具有最⼤的价值。假设⼀个0/1背包问题是，n=3，重量为w=（16，15，15），价值为v=（45，25，25），背包限重为W=30，解向量为x=（x1，x2，x3）。采⽤队列式分枝限界法求解采⽤STL的queue< NodeType >容器qu作为队列，队列中的结点类型声明如下：struct NodeType //队列中的结点类型{ int no; //结点编号，从1开始 int i; //当前结点在搜索空间中的层次 int w; //当前结点的总重量 int v; //当前结点的总价值 int x[MAXN]; //当前结点包含的解向量 double ub; //上界};现在设计限界函数，为了简便，设根结点为第0层，然后各层依次递增，显然i=n时表⽰是叶⼦结点层。由于该问题是求装⼊背包的最⼤价值，属求最⼤值问题，采⽤上界设计⽅式。对于第i层的某个结点e，⽤e.w表⽰结点e时已装⼊的总重量，⽤e.v表⽰已装⼊的总价值：如果所有剩余的物品都能装⼊背包，那么价值的上界=e.v+ (v[i+1]+…+v[n])如果所有剩余的物品不能全部装⼊背包，那么价值的上界=e.v+ (v[i+1]+…+v[k])+(物品k+1装⼊的部分重量)×物品k+1的单位价值代码int n=3,W=30;int w[]={0,16,15,15};int v[]={0,45,25,25};int maxv=-9999;int maxv=-9999;int bestx[MAXN];int total=1;struct NodeType{ int no;//节点编号，从1开始 int i;//当前节点在搜索空间中的层次 int w;//当前节点的总重量 int v;//当前节点的总价值 int x[MAXN];//当前节点包含的解向量 double ub;//上界};void bound(NodeType &e)//计算分枝节点e的上界{ int i=e.i+1;//考虑余下的物品 int sumw=e.w; double sumv=e.v; while((sumw+w[i]<=W)&&i<=n) { sumw+=w[i]; sumv+=v[i]; i++; } if(i<=n)//物品只能部分装⼊ =sumv+(W-sumw)*v[i]/w[i]; else//可以全部装⼊ =sumv;}void EnQueue(NodeType e,queue &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 { (e); }

}

void bfs(){ int j; NodeType e,e1,e2; queue qu; //根节点初始化 e.i=0; e.w=0; e.v=0; =total++; for(j=1;j<=n;j++) e.x[j]=0; bound(e); (e); (e); while (!()) { e=(); (); if(e.w+w[e.i+1]<=W)//检查左孩⼦节点 { =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); } =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(>maxv)//右剪枝 EnQueue(e2,qu); }

}采⽤优先队列式分枝限界法求解采⽤优先队列式分枝限界法求解就是将⼀般的队列改为优先队列，但必须设计限界函数，因为优先级是以限界函数值为基础的。限界函数的设计⽅法与前⾯的相同。这⾥⽤⼤根堆表⽰活结点表，取优先级为活结点所获得的价值。struct NodeType //队列中的结点类型{ int no; //结点编号 int i; //当前结点在搜索空间中的层次 int w; //当前结点的总重量 int v; //当前结点的总价值 int x[MAXN]; //当前结点包含的解向量 double ub; //上界 bool operator<(const NodeType &s) const //重载<关系函数 { return ub<; //ub越⼤越优先出队 }};代码int n=3,W=30;int w[]={0,16,15,15};int v[]={0,45,25,25};int maxv=-9999;int bestx[MAXN];int total=1;struct NodeType{ int no;//节点编号，从1开始 int i;//当前节点在搜索空间中的层次 int w;//当前节点的总重量 int w;//当前节点的总重量 int v;//当前节点的总价值 int x[MAXN];//当前节点包含的解向量 double ub;//上界 bool operator<(const NodeType &s) const { return ub<;//ub越⼤越优先出队 }};void bound(NodeType &e)//计算分枝节点e的上界{ int i=e.i+1;//考虑余下的物品 int sumw=e.w; double sumv=e.v; while((sumw+w[i]<=W)&&i<=n) { sumw+=w[i]; sumv+=v[i]; i++; } if(i<=n)//物品只能部分装⼊ =sumv+(W-sumw)*v[i]/w[i]; else//可以全部装⼊ =sumv;}void EnQueue(NodeType e,queue &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 { (e); }

}

void bfs(){ int j; NodeType e,e1,e2; priority_queue qu; //根节点初始化 e.i=0; e.w=0; e.v=0; =total++; for(j=1;j<=n;j++) e.x[j]=0; bound(e); (e); while (!()) { { e=(); (); if(e.w+w[e.i+1]<=W)//检查左孩⼦节点 { =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); } =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(>maxv)//右剪枝 EnQueue(e2,qu); }

}算法分析⽆论采⽤队列式分枝限界法还是优先队列式分枝限界法求解0/1背包问题，最坏情况下要搜索整个解空间树，所以最坏时间和空间复杂度均为O(2n)，其中n为物品个数。

2023年8月1日发(作者：)

分枝限界法求解01背包问题问题描述有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定⼀个容量为W的背包。设计从这些物品中选取⼀部分物品放⼊该背包的⽅案，每个物品要么选中要么不选中，要求选中的物品不仅能够放到背包中，⽽且重量和为W具有最⼤的价值。假设⼀个0/1背包问题是，n=3，重量为w=（16，15，15），价值为v=（45，25，25），背包限重为W=30，解向量为x=（x1，x2，x3）。采⽤队列式分枝限界法求解采⽤STL的queue< NodeType >容器qu作为队列，队列中的结点类型声明如下：struct NodeType //队列中的结点类型{ int no; //结点编号，从1开始 int i; //当前结点在搜索空间中的层次 int w; //当前结点的总重量 int v; //当前结点的总价值 int x[MAXN]; //当前结点包含的解向量 double ub; //上界};现在设计限界函数，为了简便，设根结点为第0层，然后各层依次递增，显然i=n时表⽰是叶⼦结点层。由于该问题是求装⼊背包的最⼤价值，属求最⼤值问题，采⽤上界设计⽅式。对于第i层的某个结点e，⽤e.w表⽰结点e时已装⼊的总重量，⽤e.v表⽰已装⼊的总价值：如果所有剩余的物品都能装⼊背包，那么价值的上界=e.v+ (v[i+1]+…+v[n])如果所有剩余的物品不能全部装⼊背包，那么价值的上界=e.v+ (v[i+1]+…+v[k])+(物品k+1装⼊的部分重量)×物品k+1的单位价值代码int n=3,W=30;int w[]={0,16,15,15};int v[]={0,45,25,25};int maxv=-9999;int maxv=-9999;int bestx[MAXN];int total=1;struct NodeType{ int no;//节点编号，从1开始 int i;//当前节点在搜索空间中的层次 int w;//当前节点的总重量 int v;//当前节点的总价值 int x[MAXN];//当前节点包含的解向量 double ub;//上界};void bound(NodeType &e)//计算分枝节点e的上界{ int i=e.i+1;//考虑余下的物品 int sumw=e.w; double sumv=e.v; while((sumw+w[i]<=W)&&i<=n) { sumw+=w[i]; sumv+=v[i]; i++; } if(i<=n)//物品只能部分装⼊ =sumv+(W-sumw)*v[i]/w[i]; else//可以全部装⼊ =sumv;}void EnQueue(NodeType e,queue &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 { (e); }

}

void bfs(){ int j; NodeType e,e1,e2; queue qu; //根节点初始化 e.i=0; e.w=0; e.v=0; =total++; for(j=1;j<=n;j++) e.x[j]=0; bound(e); (e); (e); while (!()) { e=(); (); if(e.w+w[e.i+1]<=W)//检查左孩⼦节点 { =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); } =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(>maxv)//右剪枝 EnQueue(e2,qu); }

}采⽤优先队列式分枝限界法求解采⽤优先队列式分枝限界法求解就是将⼀般的队列改为优先队列，但必须设计限界函数，因为优先级是以限界函数值为基础的。限界函数的设计⽅法与前⾯的相同。这⾥⽤⼤根堆表⽰活结点表，取优先级为活结点所获得的价值。struct NodeType //队列中的结点类型{ int no; //结点编号 int i; //当前结点在搜索空间中的层次 int w; //当前结点的总重量 int v; //当前结点的总价值 int x[MAXN]; //当前结点包含的解向量 double ub; //上界 bool operator<(const NodeType &s) const //重载<关系函数 { return ub<; //ub越⼤越优先出队 }};代码int n=3,W=30;int w[]={0,16,15,15};int v[]={0,45,25,25};int maxv=-9999;int bestx[MAXN];int total=1;struct NodeType{ int no;//节点编号，从1开始 int i;//当前节点在搜索空间中的层次 int w;//当前节点的总重量 int w;//当前节点的总重量 int v;//当前节点的总价值 int x[MAXN];//当前节点包含的解向量 double ub;//上界 bool operator<(const NodeType &s) const { return ub<;//ub越⼤越优先出队 }};void bound(NodeType &e)//计算分枝节点e的上界{ int i=e.i+1;//考虑余下的物品 int sumw=e.w; double sumv=e.v; while((sumw+w[i]<=W)&&i<=n) { sumw+=w[i]; sumv+=v[i]; i++; } if(i<=n)//物品只能部分装⼊ =sumv+(W-sumw)*v[i]/w[i]; else//可以全部装⼊ =sumv;}void EnQueue(NodeType e,queue &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 { (e); }

}

void bfs(){ int j; NodeType e,e1,e2; priority_queue qu; //根节点初始化 e.i=0; e.w=0; e.v=0; =total++; for(j=1;j<=n;j++) e.x[j]=0; bound(e); (e); while (!()) { { e=(); (); if(e.w+w[e.i+1]<=W)//检查左孩⼦节点 { =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); } =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(>maxv)//右剪枝 EnQueue(e2,qu); }

}算法分析⽆论采⽤队列式分枝限界法还是优先队列式分枝限界法求解0/1背包问题，最坏情况下要搜索整个解空间树，所以最坏时间和空间复杂度均为O(2n)，其中n为物品个数。