最新――动态规划解决算法0-1背包问题实验报告(含源代码)

西安邮电大学（计算机学院）课内实验报告实验名称：动态规划专业名称：计算机科学与技术班级：学生姓名：学号（8位）：指导教师：实验日期：2014年5月9日一．实验目的及实验环境1.使用动态规划法和回溯法生成两个长字符串的最优化比对结果通过实际案例，领会算法的执行效率。2.掌握动态规划、贪心算法、回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对上述方法的理解。实验环境：VisualC++6.0二.实验内容1.设计一个O（n^2）时间的算法，找出由n个数组成的序列的最长单调递增子序列2.将算法分析题3—1中算法的计算时间减至O（nlogn）3.给定n种物品和一个背包。物品i的重量是，其价值为，背包容量为C。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？三．方案设计1.动态规划的一个计算两个序列的最长公共子序列的方法如下：以两个序列X、Y为例子：设有二维数组f[i,j]表示X的i位和Y的j位之前的最长公共子序列的长度，则有：f[1][1]=same(1,1);f[i,j]=max{f[i-1][j-1]+same(i,j),f[i-1,j],f[i,j-1]}其中，same(a,b)当X的第a位与Y的第b位相同时为“1”，否则为“0”。此时，二维数组中最大的数便是X和Y的最长公共子序列的长度，依据该数组回溯，便可找出最长公共子序列。该算法的空间、时间复杂度均为O(n^2)，经过优化后，空间复杂度可为O(n)。核心代码：voidLCSL(intm,intn,int*x,int*y,intc[][N],intb[][N]){c[0][0]=0;inti,j;for(i=1;i=m;i++)c[i][0]=0;for(i=1;i=n;i++)c[0][i]=0;for(i=1;i=m;i++)for(j=1;j=m;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}coutc[m][m]endl;}voidLCS(inti,intj,int*x,intb[][N]){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);for(inty=1;yi;y++)if(x[y]==x[i])return;coutx[i];}elseif(b[i][j]==2){LCS(i-1,j,x,b);}elseLCS(i,j-1,x,b);}voidQuickSort(inta[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}通过动态规划求出最长公共子序列，再用任意排序算法，得出最长单调递增序列，我选用的排序方法是快速排序。2.一个长度为i的候选子序列的最后一个元素至少与一个长度为i-1的候选子序列的最后一个元素一样大，通过只想输入序列中元素的指针来维持候选子序列。3.0/1背包问题:现有n种物品，对1=i=n，第i种物品的重量为正整数Wi，价值为正整数Vi，背包能承受的最大载重量为正整数C，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过C且总价值尽量大。动态规划算法描述:根据问题描述，可以将其转化为如下的约束条件和目标函数：寻找一个满足约束条件，并使目标函数式达到最大的解向量，使得，而且达到最大。0-1背包问题具有最优子结构性质。假设是所给的问题的一个最优解，则是下面问题的一个最优解：。如果不是的话，设是这个问题的一个最优解，则，且。因此，，这说明是所给的0-1背包问题比更优的解，从而与假设矛盾。按照上面的情况，可以得到递推公式：设最优值为m(i,j)。max{m(i+1,j),m(i+1,j-)+}m(i,j)=m(i+1,j)nvnjwm(n,j)=00nkw#includestdio.hintV[200][200];//前i个物品装入容量为j的背包中获得的最大价值intmax(inta,intb){if(a=b)returna;elsereturnb;}intKnapSack(intn,intw[],intv[],intx[],intC){inti,j;for(i=0;i=n;i++)V[i][0]=0;for(j=0;j=C;j++)V[0][j]=0;for(i=0;i=n-1;i++)for(j=0;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]);j=C;for(i=n-1;i=0;i--){if(V[i][j]V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}printf(选中的物品是:\n);for(i=0;in;i++)printf(%d,x[i]);printf(\n);returnV[n-1][C];}voidmain(){ints;//获得的最大价值intw[15];//物品的重量intv[15];//物品的价值intx[15];//物品的选取状态intn,i;intC;//背包最大容量n=5;printf(请输入背包的最大容量:\n);scanf(%d,&C);printf(输入物品数:\n);scanf(%d,&n);printf(请分别输入物品的重量:\n);for(i=0;in;i++)scanf(%d,&w[i]);printf(请分别输入物品的价值:\n);for(i=0;in;i++)scanf(%d,&v[i]);s=KnapSack(n,w,v,x,C);printf(最大物品价值为:\n);printf(%d\n,s);}四．运行结果1.2.3.五．心得体会通过这次实验，对动态规划法求最长公共子序列有更深的理解。其实无非就是抓住书上的递推公式进行写，动态规划依赖于上一个或者上一行的解，就是在输出子序列的时候有问题。自己对动态规划、贪心、回溯法、分支限界法的原理不是非常的理解，花了很多时间看了课本上的相关内容。同时课本所提供的代码也是不能直接翻译过来用，当懂得算法的基本原理后，会发现数组下标会出错，所以在参考课本所提供的代码的同时，必须结合算法的实际情况对代码中的相关变量进行修改，这样才能充分利用课本所提供的代码完成本次实验。通过本次试验，自己基本上掌握上述算法原理，达到实验的目的。