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

算法设计与分析实验报告六学号： 1004091130 姓名： 金玉琦 日期： 2011-11-17 得分： 一、实验内容： 运用分支限界法解决0-1背包问题。 二、所用算法的基本思想及复杂度分析：分支限界法分支限界法按广度优先策略遍历问题的解空间树, 在遍历过程中, 对已经处理的每一个结点根据限界函数估算目标函数的可能取值, 从中选取使目标函数取得极值 的结点优先进行广度优先搜索, 从而不断调整搜索方向, 尽快找到问题的解。因为限界函数常常是基于问题的目标函数而确定的, 所以, 分支限界法适用于求解最优化问题。0-1背包问题 1）基本思想给定n 种物品和一个容量为C 的背包, 物品i 的重量是Wi, 其价值为Vi , 0/ 1 背包问题是如何选择装入背包的物品(物品不可分割) , 使得装入背包中物品的总价值最大，一般情况下, 解空间树中第i 层的每个结点, 都代表了对物品1 i 做出的某种特定选择, 这个特定选择由从根结点到该结点的路径唯一确定: 左分支表示装入物品, 右分支表示不装入物品。对于第i 层的某个结点, 假设背包中已装入物品的重量是w, 获得的价值是v, 计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值v, 加上背包剩余容量W - w 与剩下物品的最大单位重量价值vi + 1/ wi + 1的积,于是,得到限界函数:u b = v + ( W - w) ( vi + 1/ wi + 1 ) 根据限界函数确定目标函数的界 down , up，然后, 按照广度优先策略遍历问题的空 间树。2）复杂度分析时间复杂度是O(2n);3、 源程序及注释：#include#include#include#includeusing namespace std;int *x;struct node /结点表结点数据结构 node *parent,/父结点指针 *next; /后继结点指针 int level,/结点的层 bag,/节点的解 cw,/当前背包装载量 cp;/当前背包价值 float ub; /结点的上界值;class Knapprivate: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(); /背包问题求解;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;inext=NULL;lbestp=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 (in&wi=cleft)cleft-=wi;b+=pi;i+;if (iparent=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 ;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-ubnext=p;next1-next=no;break;next1=p;p=p-next;if(p=NULL)next1-next=no;node *Knap:nextnode()/取上限最大结点 node *p=front-next;front-next=p-next;return(p);void Knap:Sort()int i,j,k,kkl;float minl; for(i=1;in;i+) minl=1.0*pi/wi;k=0;for(j=1;j=n-i;j+) if(minl1.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=1;i-) xMi-1=bestp-bag;bestp=bestp-parent;cout变量值为:endl;for(i=1;i=n;i+)coutx(setw(2)i)=xi-1parent=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+wicp+pi)lbestp)lbestp=aa-cp+pi;bestp=nnoder(aa,1,(float)lbestp);if(long)(aa-cp)lbestp) lbestp=aa-cp;bestp=nnoder(aa,0,(float)lbestp);if(icw+wicw+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,aa-cp);if(ubblbestp) addnode(nnoder(aa,0,ubb);display();void main()int c,n;int i=0;int *p;int *w;cout请输入背包容量:c;cout请输入物品数:n; x=new intn;p=new intn;w=new intn;cout请输入n个物品的重量:endl;for(i=0;iwi; cout请输入n个物品价值:endl;for(i=0;ipi;x=new intn;Knap knbag(p,w,c,n);knbag.solvebag();getch();return; 四、运行输出结果： 五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：解决该问题首先要确定一个合适的限界函数数, 并根据限界函数确定目标函数的界down，up，然后按照广度优先策略遍历问题