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

1、 3/3动态规划解决算法0-1背包问题实验报告(含源代码) 西安邮电大学 （计算机学院） 课内实验报告 实验名称：动态规划 专业名称：计算机科学与技术 班级： 学生姓名： 学号（8位）： 指导教师： 实验日期：2014年5月9日 一实验目的及实验环境 1.使用动态规划法和回溯法生成两个长字符串的最优化比对结果通过实际案例，领会算法的执行效率。 2.掌握动态规划、贪心算法、回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对上述方法的理解。 实验环境：Visual C+ 6.0 二. 实验内容 1.设计一个O（n2）时间的算法，找出由n个数组成的序列的最长单调递增子序列

2、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”。 此时

3、，二维数组中最大的数便是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=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; cout m(n,j)= 0 0n k w #include int V200200;/前i 个物品装入容量为j 的背包中获得的最大价值 int max(int

4、 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=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;/物品的选取状态 in

5、t n,i; int C;/背包最大容量 n=5; printf(请输入背包的最大容量:n); scanf(%d, printf(输入物品数:n); scanf(%d, printf(请分别输入物品的重量:n); for(i=0;in;i+) scanf(%d, printf(请分别输入物品的价值:n); for(i=0;in;i+) scanf(%d, s=KnapSack(n,w,v,x,C); printf(最大物品价值为:n); printf(%dn,s); 四运行结果 1. 2. 3. 五心得体会 通过这次实验，对动态规划法求最长公共子序列有更深的理解。其实无非就是抓住书上的递推公式进行写，动态规划依赖于上一个或者上一行的解，就是在输出子序列的时候有问题。自己对动态规划、贪心、回溯法、分支限界法的原理不是非常的理解，花了很多时间看了课本上的相关内容。同时课本所提供的代码也是不能直接翻译过来用，当懂得算法的基本原理后，会发现数组下标会出错，所以在参考课本所