01背包问题实验报告

算法设计与分析实验报告书实验名称：0/1背包问题学号：姓名：实验时间：2015年6月1日《算法分析与设计》实验报告-1-一实验目的和要求（1）深刻掌握贪心法、动态规划法、回溯法的设计思想并能熟练运用（2）理解这样一个观点：同样的问题可以用不同的方法来解决，一个好的算法是反复努力和重新修正的结果。二实验内容（1）分别用蛮力法贪心法、动态规划法、回溯法设计0/1背包问题的算法。（2）分析算法随n和C变化的时间性能，随机产生参数n和C，收集算法执行的时间（3）讨论n和C变化时，动态规划法和回溯法的时间性能。（4）讨论几种算法在该问题求解上的特点。三实验环境VC++6.0四设计思想及实验步骤蛮力法的设计思想和步骤将所有排列下的背包的重量和价值都计算出来，选择重量不大于背包的总重量下的最大价值。贪心法的设计思想和步骤首先计算每种物品单位重量的价值vi/wi；按单位价值对物品进行升序排列。然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入《算法分析与设计》实验报告-2-背包，直到背包装满为止。动态规划法的设计思想和步骤令V(i,j)表示在前i个物品中能够装入容量为j的背包中的物品的最大价值，则可以得到如下动态函数：V（i,j）=0(i=0或j=0)V(i,j)=V(i-1,j)jw[i]V(i,j)=max{V(i-1,j),V(I,j-1)+v[i]}j=w[j]按照下述方法来划分段：第一段只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入2个物品，确定在各种情况下的背包能够得到的最大价值；以此类推，直到第n个阶段。最后V(n,C)便是容量为C的背包中装入n个物品时获取到的最大价值。回溯法的设计思想和步骤为了避免生成那些不可能产生最佳解的问题状态，要不断的利用越约束条件来剪掉那些实际上不可能产生所需解的节点，以减少问题额计算量。对于n种可选物品的0/1背包问题，其解空间长度由长度为n的0-1向量组成，可用子集数表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索进入左子树，否则返回上一节点，搜索右子数。时间测试的设计思想蛮力法由于需要考虑每一种情况所以物品的个数不能太多，所以设计时间测试函数在1到32的范围内随机残生物品的个数n，然后在随机产生n《算法分析与设计》实验报告-3-个物品每个物品的重量和价值，将背包容量设为n个物品总重量的一半，求出最优解。重复执行背包求解过程，然后求出其平均时间消耗。算法描述如下：蛮力法：输入：物品总数n，每个物品的重量w[i]和价值v[i]，背包容量C输出：背包所装物品的最大总价值1.求出2的n次方2.循环i从1到m-1，2.1求出i的二进制2.2根据i的二进制序列，判断重量和是否小于或等于C，如果等于则求出总价值value，2.3如果valuemaxValue,则maxValue=value;，并把该二进制序列T复制到S数组中以记录最优解。贪心法：输入：物品总数n，每个物品的重量w[i]和价值v[i]，背包容量C输出：背包所装物品的最大总价值1.将每个物品的重量和价值存放到保存物品信息的结构体node[]中2.将node数组中的物品暗中单位价值的大小从大到小排序3.Temp=C;4.循环i从1到n《算法分析与设计》实验报告-4-如果node[i].w=temp，将物品放入背包，标记node[i]=1;temp-=node[i].w;i++;如果temp=0背包被装满，结束循环。动态规划法输入：物品总数n，每个物品的重量w[i]和价值v[i]，背包容量C输出：背包所装物品的最大总价值1.初始化过程图2.双重循环，逐步求出将前i个物品放到容量为j的背包获得的最大价值for(i=1;i=n;i++)for(j=1;j=C;j++)如果jw[i],则V[i][j]=V[i-1][j];否则V[i][j]=Max(V[i-1][j],V[i-1][j-w[i]]+v[i]);3.回溯求得最优解循环for(j=C,i=n;i0;i--)如果V[i][j]V[i-1][j]，则x[i]=1;j=j-w[i];否则x[i]=0;回溯法（递归）输入：物品总数n，每个物品的重量w[i]和价值v[i]，背包容量C输出：背包所装物品的最大总价值1.从第一个物品开始,t=1;《算法分析与设计》实验报告-5-2.如果legal(t)=1,则backTrack（t+1）分析下一个物品3.如果tn，求出背包的总价值value，如果value大于最大价值，则把最大价值更新，同时更新记录物品装入情况的数组P,以记录最优解。六核心源代码#includeiostream#includealgorithm#includestdlib.h#includestdio.h#includetime.h#includewindows.husingnamespacestd;intw[505],v[505],n;longC;//回溯法intp[500],P[500];//回溯法中分别记录当前解和最优解的状态数组intValue=0;//回溯法中的最大价值boollegal(intt){intsum=0;for(inti=1;i=t;i++)sum+=w[i]*p[i];if(sumC)returnfalse;elsereturntrue;}voidbackTrack(intt){if(tn)《算法分析与设计》实验报告-6-{inti;intvalue=0;for(i=1;i=n;i++){value+=v[i]*p[i];//coutp[i];}if(valueValue){Value=value;for(i=1;i=n;i++)P[i]=p[i];}}else{for(inti=1;i=0;i--){p[t]=i;if(legal(t))backTrack(t+1);}}}intBack(){backTrack(1);returnValue;}//动态规划法《算法分析与设计》实验报告-7-intMax(inta,intb){returnab?a:b;}intKnapSack(){//动态规划法intV[505][505];intx[1005];inti,j;for(i=0;i=n;i++)//初始化第0列V[i][0]=0;for(j=0;j=C;j++)V[0][j]=0;//初始化第0行for(i=1;i=n;i++)for(j=1;j=C;j++)if(jw[i])V[i][j]=V[i-1][j];elseV[i][j]=Max(V[i-1][j],V[i-1][j-w[i]]+v[i]);for(j=C,i=n;i0;i--){if(V[i][j]V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}returnV[n][C];}《算法分析与设计》实验报告-8-//蛮力法intForce(){//蛮力法intmaxValue=0;intm=1n;intS[32],T[32];for(inti=1;im;i++){intt=1;inttemp=i;while(temp){T[t++]=temp%2;temp=temp/2;}intj;/*for(j=1;jt;j++)coutT[j];*/intweight=0,value=0;for(j=1;jt;j++){if(T[j]==1&&weight+w[j]=C){weight=weight+w[j];value=value+v[j];}}if(maxValuevalue){maxValue=value;intk=0;for(j=0;jt;j++)《算法分析与设计》实验报告-9-{S[k++]=T[j];}}}returnmaxValue;}//贪心法structNode{inti;doublew,v;}node[500];intcmp(Nodea,Nodeb){return(a.v/a.w)(b.v/b.w);}intgreed(){inti;intmaxValue=0;for(i=1;i=n;i++){node[i].i=0;node[i].w=w[i];node[i].v=v[i];}sort(node+1,node+n+1,cmp);/*for(i=1;i=n;i++){coutnode[i].wnode[i].vendl;《算法分析与设计》实验报告-10-}*/inttemp=C;i=1;while(temp&&(i=n)){if(node[i].w=temp){maxValue+=node[i].v;node[i].i=1;temp-=node[i].w;//coutnode[i].w;}i++;}returnmaxValue;}intRandom(){return(rand()%(1000)+1);}voidtext(int(*matter)()){LARGE_INTEGERlitmp;LONGLONGstart,over;doubledfMinus,dfFreq,dfTim;QueryPerformanceFrequency(&litmp);dfFreq=(double)litmp.QuadPart;QueryPerformanceCounter(&litmp);start=litmp.QuadPart;for(intk=0;k100;k++){C=0;《算法分析与设计》实验报告-11-n=Random()%30;for(inti=1;i=n;i++){w[i]=Random();v[i]=Random();C=C+w[i];}C=C/2;matter();//coutmatter()endl;}QueryPerformanceCounter(&litmp);over=litmp.QuadPart;dfMinus=(double)(over-start);dfTim=dfMinus/dfFreq/100;cout平均时间T(k):;printf(%e\t,dfTim);coutendl;}intmain(){cout先测试算法的正确性endl;n=4;C=10;w[1]=7;w[2]=3;w[3]=4;w[4]=5;v[1]=42;v[2]=12;v[3]=40;v[4]=25;cout蛮力法Force()endl;cout贪心法greed()endl;cout动态规划法KnapSack()endl;cout回溯法Back()endl;cout测试时间效率：endl;srand((unsigned)time(NULL));《算法分析与设计》实验报告-12-cout动态规划法的执行时间：endl;cout蛮力法的执行时间：endl;text(Force);cout贪心法的执行时间endl;text(greed);cout动态规划法的执行时间endl;text(KnapSack);cout回溯法的执行时间endl;text(Back);return0;}七实验结果及分析下面的结果是每个算法都分别运行50次后的平均运行时间：根据结果可以得出，蛮力算法的效率是最低的，回溯算法的时间效率优势很明显是最高的，而贪心法和动态规划的效率也均高于蛮力法，且二者相差不明显。蛮力法时间复杂性分析：对于n个元素的集合，其子集数量时2n,所以不论生成子集的算法效率有多高，蛮力法求接0/1背包问题都会导致一个下界为2n的算法。蛮力法的特点：蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。贪心法时间复杂性分析：《算法分析与设计》实验报告-13-贪心法首选对物品进行了排序，按照价值/重量将序排列，此处采用的是快速排序，时间复杂性为O(nlogn);