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

西 安 邮 电 大 学 （计算机学院）课内实验报告实验名称： 动态规划 专业名称： 计算机科学与技术班 级： 学生姓名： 学号（8位）： 指导教师： 实验日期： 2014年5月9日1 实验目的及实验环境1. 使用动态规划法和回溯法生成两个长字符串的最优化比对结果通过实际案例，领会算法的执行效率。2. 掌握动态规划、贪心算法、回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对上述方法的理解。实验环境：Visual C+ 6.0二. 实验内容1.设计一个O（n2）时间的算法，找出由n个数组成的序列的最长单调递增子序列2.将算法分析题31中算法的计算时间减至O（nlogn）3.给定n种物品和一个背包。物品i的重量是，其价值为，背包容量为C。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？三方案设计1. 动态规划的一个计算两个序列的最长公共子序列的方法如下：以两个序列 X、Y 为例子：设有二维数组fi,j 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则有：f11 = same(1,1);fi,j = maxfi-1j -1 + same(i,j),fi-1,j,fi,j-1其中，same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”，否则为“0”。此时，二维数组中最大的数便是 X 和 Y 的最长公共子序列的长度，依据该数组回溯，便可找出最长公共子序列。该算法的空间、时间复杂度均为O(n2)，经过优化后，空间复杂度可为O(n)。核心代码：void LCSL(int m,int n,int *x,int *y,int cN,int bN)c00=0; int i,j; for(i=1;i=m;i+) ci0=0; for(i=1;i=n;i+) c0i=0; for(i=1;i=m;i+) for(j=1;j=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; coutcmmendl;void LCS(int i,int j,int *x,int bN) if(i=0|j=0) return; if(bij=1) LCS(i-1,j-1,x,b);for(int y=1;yi;y+) if(xy=xi) return; coutxi ; else if(bij=2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); void QuickSort(int a,int p,int r) if(pr) int q=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)。 maxm( i+1, j ), m( i+1, j-)+ m( i, j )=m(i+1,j) m(n,j)= 0 #include int V200200;/前i个物品装入容量为j的背包中获得的最大价值 int max(int a,int b) if(a=b) return a; else return b; int KnapSack(int n,int w,int v,int x,int C) int i,j; for(i=0;i=n;i+) Vi0=0; for(j=0;j=C;j+) V0j=0; for(i=0;i=n-1;i+) for(j=0;j=C;j+) if(j=0;i-) if(VijVi-1j) xi=1; j=j-wi; else xi=0; printf(选中的物品是:n); for(i=0;in;i+) printf(%d ,xi); printf(n); return Vn-1C; void main() int s;/获得的最大价值 int w15;/物品的重量 int v15;/物品的价值 int x15;/物品的选取状态 int n,i; int C;/背包最大容量 n=5; printf(请输入背包的最大容量:n); scanf(%d,&C); printf(输入物品数:n); scanf(%d,&n); printf(请分别输入物品的重量:n); for(i=0;in;i+) scanf(%d,&wi); printf(请分别输入物品的价值:n); for(i=0;in;i+) scanf(%d,&vi); s=KnapSack(n,w,v,x,C); printf(最大物品价值为:n); printf(%dn,s); 4 运行结果 1.2.3.五心得体会 通过这次实验，对动态规划法求最长公共子序列有更深的理解。其实无非就是抓住书上的递推公式进行写，动态规划依赖于上一个或者上一行的解，就是在输出子序列的时候有问题。自己对动态规划、贪心、回溯法、分支限界法的原理不是非常的理解，花了很多时间看了课本上的相关内容。同时课本所提供的