一.分支限界法概述
(1)分支限界法就是采用广度优先的策略,依次搜索活结点所有的分枝,也就额是所有的相邻结点。在求最优解时采用一个限界函数,计算限界函数值,选择一个最有利的子节点作为扩展结点,使搜索树朝着解空间树上有最优解的分支推进,以便尽快找出一个最优解。
(2)常见的两种分支限界法
先进先出(FIFO)队列式:在先进先出的分支限界法中,用队列作为组织活结点表的数据结构,并按照队列先进先出的原则选择结点作为扩展结点。
优先队列(PQ):用优先队列作为组织活结点表的数据结构。
二.0-1背包问题
问题:给定n种物品和一背包。物品i的重量是wi,其价值为pi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
#include<iostream> #include<queue> using namespace std; const int maxn=99; int n,c; int w[maxn]; int v[maxn]; int bestv=0; int bestx[maxn]; int total=1; //解空间中的节点数累计,全局变量 struct nodetype //队列中的结点类型 { int no; //结点编号,从1开始 int i; //当前结点在搜索空间中的层次 int w; //当前结点的总重量 int v; //当前结点的总价值 int x[maxn]; //当前结点包含的解向量 double ub; //上界 }; void input() { cout<<"请输入物品的个数:"<<endl; cin>>n; cout<<"请输入每个物品的重量及价值(如5 4):"<<endl; for(int i = 1; i <= n; i++) { cin>>w[i]>>v[i]; } cout<<"请输入背包的容量:"<<endl; cin>>c; } void bound(nodetype &e) //计算分支结点e的上界 { int i=e.i+1; //考虑结点e的余下物品 int sumw=e.w; double sumv=e.v; while((sumw+w[i]<=c)&&i<=n) { sumw+=w[i]; sumv+=v[i]; i++; } if(i<=n) //余下物品只能部分装入 e.ub=sumv+(c-sumw)*v[i]/w[i]; else e.ub=sumv; } void enqueue(nodetype e,queue<nodetype> &qu) //结点e进队qu { if(e.i==n) //到达叶子节点,不在扩展对应一个解 { if(e.v>bestv) //找到更大价值的解 { bestv=e.v; for(int j=1;j<=n;j++) bestx[j]=e.x[j]; } } else qu.push(e); //非叶子结点进队 } void bfs() { int j; nodetype e,e1,e2; queue<nodetype> qu; e.i=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.front();qu.pop(); //出队结点e if(e.w+w[e.i+1]<=c) //剪枝,检查左孩子结点 { 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(e2.ub>bestv) //若右孩子结点可行,则进队,否则被剪枝 enqueue(e2,qu); } } void output() { cout<<"最优值是:"<<bestv<<endl; cout<<"("; for(int i=1;i<=n;i++) cout<<bestx[i]<<" "; cout<<")"; } int main() { input(); bfs(); output(); return 0; }