实验5 分支界限法解0-1背包问题一、实验要求1．要求用分支界限法求解0-1背包问题；2．要求交互输入背包容量，物品重量数组，物品价值数组；3．要求显示结果。
二、实验仪器和软件平台仪器：带usb接口微机软件平台：WIN-XP + VC++三、源程序#include ""#include<iostream>#include<cstdio>#include<>#include<iomanip>using namespace std;int *x;struct node //结点表结点数据结构{node *parent;//父结点指针node *next; //后继结点指针int level;//结点的层int bag;//节点的解int cw;//当前背包装载量int cp;//当前背包价值float ub; //结点的上界值};//类Knap中的数据记录解空间树中的结点信息，以减少参数传递及递归调用所需的栈空间class Knap{private:struct node *front, //队列队首*bestp,*first; //解结点、根结点int *p,*w,n,c,*M;//背包价值、重量、物品数、背包容量、记录大小顺序关系 long lbestp;//背包容量最优解public:void Sort();Knap(int *pp,int *ww,int cc,int nn);~Knap();float Bound(int i,int cw,int cp);//计算上界限node *nnoder(node *pa,int ba,float uub);//生成一个结点 ba=1生成左节点 ba=0生成右节点void addnode(node *nod);//向队列中添加活结点void deletenode(node *nod);//将结点从队列中删除struct node *nextnode(); //取下一个节点void display(); //输出结果void solvebag(); //背包问题求解};//按物品单位重量的价值排序void Knap::Sort(){int i,j,k,kkl;float minl;for(i=1;i<n;i++){minl=*p[i]/w[i];k=0;for(j=1;j<=n-i;j++){if(minl<*p[j]/w[j]){minl=*p[j]/w[j];swap(p[k],p[j]);swap(w[k],w[j]);swap(M[k],M[j]);k=j;}}}}Knap::Knap(int *pp,int *ww,int cc,int nn) {int i;n=nn;c=cc;p=new int[n];w=new int[n];M=new int[n];for(i=0;i<n;i++){p[i]=pp[i];w[i]=ww[i];M[i]=i; //用M数组记录大小顺序关系}front=new node[1];front->next=NULL;lbestp=0;bestp=new node[1];bestp=NULL;Sort();}Knap::~Knap(){delete []first;delete []front;delete []bestp;delete []p;delete []w;}//取上限最大结点node *Knap::nextnode(){node *p=front->next;front->next=p->next;return(p);}//将一个新的结点插入到子集树和优先队列中node * Knap::nnoder(struct node *pa,int ba,float uub) {//生成一个新结点node * nodell=new(node);nodell->parent=pa;nodell->next=NULL;nodell->level=(pa->level)+1;nodell->bag=ba;nodell->ub=uub;if(ba==1){nodell->cw=pa->cw+w[pa->level];nodell->cp=pa->cp+p[pa->level] ;}else{nodell->cw=pa->cw;nodell->cp=pa->cp;}return(nodell);}//将结点加入优先队列void Knap::addnode(node *no){node *p=front->next,*next1=front;float ub=no->ub;while(p!=NULL){if(p->ub<ub){no->next=p;next1->next=no;break;}next1=p;p=p->next;}if(p==NULL){next1->next=no;}}// 计算结点所相应价值的上界float Knap::Bound(int i,int cw,int cp){int cleft=c-cw; //剩余容量float b=(float)cp; //价值上界//以物品单位重量价值减序装填剩余容量while (i<n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装填剩余容量装满背包if (i<n) b+=*p[i]/w[i]*cleft;return b;}//计算最优值和变量值void Knap::display(){int i;cout<<endl;cout<<"当前最优价值为:"<<lbestp<<endl;for(i=n;i>=1;i--){x[M[i-1]]=bestp->bag;bestp=bestp->parent;}cout<<"变量值 x = ";for(i=1;i<=n;i++)cout<<x[i-1];cout<<endl;}//背包问题求解void Knap::solvebag(){int i;float ubb;node *aa; //记录上限最大结点first=new node[1]; //根结点first->parent=NULL;first->next=NULL;first->level=0; //用level记录结点的层first->cw=0;first->cp=0;first->bag=0;ubb=Bound(0,0,0);first->ub=ubb;front->next=first;while(front->next!=NULL){aa=nextnode();i=aa->level;//当叶子节点处的解>最优解时，更新最优解if(i==n-1){if(aa->cw+w[i]<=c&&(long)(aa->cp+p[i])>lbestp){lbestp=aa->cp+p[i];bestp=nnoder(aa,1,(float)lbestp);//将一个新的结点插入到子集树和优先队列中}if((long)(aa->cp)>lbestp){lbestp=aa->cp;bestp=nnoder(aa,0,(float)lbestp);}}//非叶子结点，递归调用Bound函数计算上界if(i<n-1){if(aa->cw+w[i]<=c&&Bound(i+1,aa->cw+w[i],aa->cp+p[i])>(float)lbestp) {ubb=Bound(i,aa->cw+w[i],aa->cp+p[i]);addnode(nnoder(aa,1,ubb));//将结点加入到优先队列中}ubb=ubb=Bound(i,aa->cw,aa->cp);if(ubb>lbestp)addnode(nnoder(aa,0,ubb));}}display();}int main(){int c,n;int i=0;int *p;int *w;cout<<endl;cout<<"|***********分支限界法解0-1背包问题***********| "<<endl;cout<<endl;cout<<"请输入物品数量 n = ";cin>>n;cout<<endl;cout<<"请输入背包容量 C = ";cin>>c;cout<<endl;x=new int[n]; //变量值p=new int[n]; //物品价值w=new int[n]; //物品重量cout<<"请分别输入这"<<n<<"个物品的重量W:"<<endl;for(i=0;i<n;i++)cin>>w[i];cout<<endl;cout<<"请输入这"<<n<<"个物品的价值P:"<<endl;for(i=0;i<n;i++)cin>>p[i];Knap knbag(p,w,c,n);();getch();return 0;}四、运行结果五、实验小结回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。