实验报告8-蛮力动态规划01背包

PAGEPAGE10《算法设计与分析》实验报告八学号：1004091130姓名：金玉琦日期：2011-12-5得分：一、实验内容：分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。二、所用算法的基本思想及复杂度分析：蛮力法基本思想用蛮力法求解就是要穷举出物品的所有组合，计算不超过背包容量的物品的最大价值和复杂度分析装法有2n种组合，每种组合中又要计算价值和，所以其复杂度为指数级。动态规划法基本思想动态规划法的关键在于找到决策函数，在本例中，令V(i,j)表示在前i个物品中能够装入容量为j的背包中的物品的最大值,则有如下动态规划函数：V(i,0)=V(0,j)=0; (1) V(i-1,j) j<wiV(i,j)= (2) max{V(i-1,j),V(i-1,j-wi)+vi} j>=wi式(1)表明：把前面i个物品的装入容量为0的背包和把0个物品装入容量为j的背包，得到的总价值都是0。式(2)的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：1.如果把第i个物品装入背包，则背包中的物品价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；2.如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然取二者的较大值作为把前i个物品装入容量为j的背包中的最优解。复杂度分析时间复杂度是O(n*c)。回溯法基本思想回溯法是一种有组织的系统化搜索技术，可以看作是蛮力法穷举搜索的一种改进。具体在0/1背包问题中的使用如下：回溯法从0/1背包问题的解空间树的根节点出发，按照深度优先遍历解空间树，搜索满足约束条件的解。在搜索到树中的任一结点时，先判断该结点的对应部分的解是否满足约束条件，或者是否超出目标函数的界,也就是判断该结点是否包含问题的(最优)解，如果不包含则跳过对以该结点为根的子树的搜索；否则进入以该结点为根的子树继续深度优先遍历搜索。复杂度分析0/1背包问题的解空间树是一棵子集树，遍历一棵子集树所需时间为Ω(2n)。分支限界法基本思想分支限界法按照广度优先法遍历整个解空间树，在遍历过程中，对已经处理过的每一个结点根据限界函数估算目标函数的可能值，从中选取使目标函数取得极大或极小的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的最优解。复杂度分析由于分治限界法是蛮力法的一种改进，所以在0/1背包问题中，问题的复杂度在最坏的情况下是指数阶的。三、源程序及注释：#defineMAX100#definemax(a,b)(a>b)?a:b#include<MATH.H>#include<VECTOR>#include<stdio.h>#include<stdlib.h>#include<WINDOWS.H>#include<TIME.H>#include<IOSTREAM>#include<algorithm>usingnamespacestd;//设计物品属性，重量和价值typedefstruct{ doublew; //重量 doublev; //价值}OBJECT;//回溯法intbestV=0; //最大价值intcw=0; //当前重量intcv=0; //当前价值//进入右子树条件intR_Bentch(inti,intn,intc,OBJECTt[]){ intj=i; intleft_C=c-cw; inttempV=cv; while(t[j].w<left_C&&j<n) { left_C-=t[j].w; tempV+=t[j].v; j++; } returntempV;}//递归voidBackTrack(inti,intn,intc,OBJECTt[]){ if(i>=n) { if(bestV<cv) bestV=cv; return; } if(cw+t[i].w<=c) //进入左子树 { cw+=t[i].w; cv+=t[i].v; BackTrack(i+1,n,c,t); cw-=t[i].w; //回溯前回复到上一状态 cv-=t[i].v; } if(R_Bentch(i+1,n,c,t)>bestV) //进入右子树 BackTrack(i+1,n,c,t); }//分支限界//状态结构体typedefstruct{ bools1[MAX]; //当前放入物体 intk; //搜索深度 doubleb; //价值上界 doublew; //物体重量 doublev; //物体价值}KNAPNODE;//堆元素结构体typedefstruct{ KNAPNODE*p; //结点数据 doubleb; //所指结点的上界}HEAP;//比较两个物体价值比intcmp(OBJECTa,OBJECTb){ returna.v/a.w>b.v/b.w;}//交换两个堆元素voidswap(HEAP&a,HEAP&b){ HEAPtemp=a; a=b; b=temp;}//堆中元素上移voidsift_up(HEAPH[],inti){ booldone=false; if(i!=1) { while(!done&&i!=1) { if(H[i].b>H[i/2].b) swap(H[i],H[i/2]); else done=true; i=i/2; } }}//堆中元素下移voidsift_down(HEAPH[],intn,inti){ booldone=false; if((2*i)<=n) { while(!done&&((i=2*i)<=n)) { if(i+1<=n&&H[i+1].b>H[i].b) i++; if(H[i/2].b<H[i].b) swap(H[i/2],H[i]); else done=true; } }}//往堆中插入结点voidinsert(HEAPH[],HEAPx,int&n){ n++; H[n]=x; sift_up(H,n);}//删除堆中的结点voiddel(HEAPH[],int&n,inti){ HEAPx,y; x=H[i]; y=H[n]; n--; if(i<=n) { H[i]=y; if(y.b>=x.b) sift_up(H,i); else sift_down(H,n,i); }}//获得堆顶元素并删除HEAPdelete_max(HEAPH[],int&n){ HEAPx=H[1]; del(H,n,1); returnx;}//计算分支结点的上界voidbound(KNAPNODE*node,doubleM,OBJECTob[],intn){ inti=node->k; doublew=node->w; doublev=node->v; if(node->w>M) { //物体重量超过背包的容量 node->b=0; //上界置为0 } else { while((w+ob[i].w<=M)&&(i<n)) { w+=ob[i].w; //计算背包已载入载重 v+=ob[i++].v; //计算背包已装入价值 } if(i<n) node->b=v+(M-w)*ob[i].v/ob[i].w; else node->b=v; }}//分支限界求解函数//输入：n个物体的重量和价值数组ob[]，背包载重M//输出：装入背包的物体最优价值vdoubleknapsack_bound(OBJECTob[],doubleM,intn){ inti,k=0; //堆中元素个数计数器初始化为0 doublev; KNAPNODE*xnode,*ynode,*znode; HEAPx,y,z,*heap; heap=newHEAP[n*n]; //分配堆的存储空间 sort(ob,ob+n,cmp); //对物体按照价值重量比排序 xnode=newKNAPNODE; //建立父结点 for(i=0;i<n;i++) //初始化结点 xnode->s1[i]=false; xnode->k=xnode->w=xnode->v=0; while(xnode->k<n) { ynode=newKNAPNODE; //建立y结点 *ynode=*xnode; //结点x的数据复制到y ynode->s1[ynode->k]=true; //装入第k个物体 ynode->w+=ob[ynode->k].w; //背包中物体的累计重量 ynode->v+=ob[ynode->k].v; //背包中物体的累计价值 ynode->k++; //搜索深度++ bound(ynode,M,ob,n); //计算结点y的上界 y.b=ynode->b; y.p=ynode; insert(heap,y,k); //结点y按上界的值插入到堆中 znode=newKNAPNODE; //建立结点z *znode=*xnode; //结点x数据复制到z znode->k++; //搜索深度++ bound(znode,M,ob,n); //计算结点z的上界 z.b=znode->b; z.p=znode; insert(heap,z,k); //结点z按上界的值插入堆中 deletexnode; x=delete_max(heap,k); //获得堆顶元素作为新的父亲结点 xnode=x.p; } v=xnode->b; deletexnode; deleteheap; returnv; //返回背包中物体的价值}//动态规划doubleKnapSack(intn,intc,OBJECTob[]){ inti,j; vector<vector<double>>V(n+1,vector<double>(c+1)); for(i=0;i<=n;i++) V[i][0]=0; for(j=0;j<=c;j++) V[0][j]=0; for(i=1;i<=n;i++) { for(j=1;j<=c;j++) { if(j<ob[i].w) V[i][j]=V[i-1][j]; else V[i][j]=max(V[i-1][j],V[i-1][j-ob[i].w]+ob[i].v);/* cout<<V[i][j]<<"";*/ }/* cout<<endl;*/ } returnV[n][c];}//蛮力法voidconversion(intn,intb[MAX])//将n化为二进制形式，结果存放到数组b中{inti;for(i=0;i<MAX;i++) { b[i]=n%2; n=n/2; if(n==0)break; }}doubleForce(intn,intc,OBJECTob[]){ inti,j; intb[MAX]; doublemaxv; doubletemp_v,temp_w; maxv=0; //分别求出所有的子集，按要求寻找最大的子集for(i=0;i<pow(2,n);i++) {for(j=0;j<n;j++) { b[j]=0; }conversion(i,b);temp_v=0;temp_w=0; for(j=0;j<n;j++) { if(b[j]==1) { temp_w=temp_w+ob[j].w; temp_v=temp_v+ob[j].v; } } if((temp_w<=c)&&(temp_v>=maxv)) maxv=temp_v; } returnmaxv;}//主函数===============================================voidmain(){ OBJECTt[MAX]; intn; //实际物品数 intc; //背包容量 inti; //测时间 LARGE_INTEGERbegin,end,frequency; QueryPerformanceFrequency(&frequency); //输入 cout<<"输入物品总数:"; cin>>n; cout<<"输入背包的总容量:"; cin>>c; srand(time(0)); for(i=0;i<n;i++) { t[i].w=rand()%11+rand()%17; t[i].v=rand()%37+rand()%61; cout<<"第"<<i+1<<"个物品重量:"<<t[i].w <<"价值:"<<t[i].v<<endl; } //分支限界 doublemaxV; QueryPerformanceCounter(&begin); maxV=knapsack_bound(t,c,n); QueryPerformanceCounter(&end); cout<<"**************分支限界法********************"<<endl; cout<<"结果:"<<maxV<<endl; cout<<"时间:" <<(double)(end.QuadPart-begin.QuadPart)/frequency.QuadPart <<"s"<<endl; //动态规划 QueryPerformanceCounter(&begin); maxV=KnapSack(n,c,t); QueryPerformanceCounter(&end); cout<<"**************动态规划法********************"<<endl; cout<<"结果:"<<maxV<<endl; cout<<"时间:" <<(double)(end.QuadP