试验报告分支限界法01背包

1、算法设计与分析实验报告六学号：1004091130姓名：金玉琦日期： 2011-11-17得分：8、实验内容:运用分支限界法解决0-1背包问题。二、所用算法的基本思想及复杂度分析：分支限界法,在遍历过程中，对已经处理的,从中选取使目标函数取得极值分支限界法按广度优先策略遍历问题的解空间树每一个结点根据限界函数估算目标函数的可能取值的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。因为限界 函数常常是基于问题的目标函数而确定的，所以，分支限界法适用于求解最优化问题。0-1背包问题1) 基本思想给定n种物品和一个容量为 C的背包，物品i的重量是W,其价值为Vi，0/ 1背包问题是

2、如何选择装入背包的物品(物品不可分割)，使得装入背包中物品的总价值最大，一般情况下，解空间树中第i层的每个结点，都代表了对物品1i做出的某种特 定选择，这个特定选择由从根结点到该结点的路径唯一确定：左分支表示装入物品，右分支表示不装入物品。对于第i层的某个结点，假设背包中已装入物品的重量是w获得的价值是v，计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物 品取得的价值v，加上背包剩余容量 W- w与剩下物品的最大单位重量价值vi + 1/ wi +1的积，于是，得到限界函数：u b = v + ( W- w) x( vi + 1/ wi + 1 )根据限界函数确定目标函数的界dow

3、n，up，然后，按照广度优先策略遍历问题的空间树。2) 复杂度分析时间复杂度是O(2n);三、源程序及注释：#include<iostream>#include<cstdio>#include<conio.h>#include<iomanip>using namespace std;int *x;struct node(/结点表结点数据结构node *parent,/父结点指针*next; /后继结点指针int level,/结点的层bag,/cw,/节点的解当前背包装载量cp;/当前背包价值float ub; /结点的上界值）；class Kn

4、apprivate: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);/void addnode(node *nod);/void deletenode

5、(node *nod);/struct node *nextnode(); /输出结果void display(); /计算上界限生成一个结点ba=1生成左节点ba=0生成右节将结点添加到队列中将结点队列中删除取下一个void solvebag(); / 背包问题求解Knap:Knap(int *pp,int *ww,int cc,int nn)int i;n=nn;c=cc;p=new intn;w=new intn;M=new intn;for(i=0;i<n;i+)pi=ppi;wi=wwi;Mi=i;front=new node1;front->next=NULL;lbes

6、tp=0;bestp=new node1;bestp=NULL;Sort();)Knap:Knap()delete first;delete front;delete bestp;delete p;delete w;)float Knap:Bound(int i,int cw,int cp)/计算上界int cleft=c-cw;float b=(float)cp;while (i<n&&wi<=cleft)cleft-=wi;b+=pi;i+;)if (i<n) b+=1.0*pi/wi*cleft;return b;)node * Knap:nnoder(

7、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+wpa->level;nodell->cp=pa->cp+ppa->level;)elsenodell->cw=pa->cw;nodell->

8、;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;node *Knap:nextnode()/取上限最大结点node *p=front->next;fro

9、nt->next=p->next;return(p);void Knap:Sort()int i,j,k,kkl;float minl;for(i=1;i<n;i+)minl=1.0*pi/wi;k=0;for(j=1;j<=n-i;j+)if(minl<1.0*pj/wj)minl=1.0*pj/wj;swap(pk,pj);swap(wk,wj);swap(Mk,Mj);k=j;void Knap:display()int i;cout<<"最大价值是:"<<lbestp<<endl;for(i=n;i&

10、gt;=1;i-)(xMi-1=bestp->bag;bestp=bestp->parent;cout<<"变量值为:"<<endl;for(i=1;i<=n;i+)cout<<"x("<<setw(2)<<i<<")="<<xi-1<<endl;void Knap:solvebag()(/背包问题求解int i;float ubb;node *aa;first=new node1; / 根结点first->pare

11、nt=NULL;first->next=NULL;first->level=0;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+wi<=c&&(long)(aa->cp+pi)>lbestp)(lbestp=aa->cp+pi;bes

12、tp=nnoder(aa,1,(float)lbestp);if(long)(aa->cp)>lbestp)(lbestp=aa->cp;bestp=nnoder(aa,0,(float)lbestp);if(i<n-1)(if(aa->cw+wi<=c&&Bound(i+1,aa->cw+wi,aa->cp+pi)>(float)lbestp)(ubb=Bound(i,aa->cw+wi,aa->cp+pi);addnode(nnoder(aa,1,ubb);ubb=ubb=Bound(i,aa->cw,

13、aa->cp);if(ubb>lbestp)addnode(nnoder(aa,0,ubb);display();void main()(int c,n;int i=0;int *p;int *w;cout<<"请输入背包容量:"<<endl;cin>>c;cout<<"请输入物品数:"<<endl;cin>>n;x=new intn;p=new intn;w=new intn;cout<<"请输入"<<n<<"个物品的重量:"<<endl;for(i=0;i<n;i+)cin>>wi;cout<<"请输入"<<n<<"个物品价值:"<<endl;for(i=0;i<n;i+)cin>>pi;x=new intn;Knap knbag(p,w,c,n);knbag.solvebag();getch();return;四、运行输出结果:五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：解决该问题首先