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

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

2、间减至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 的最长公共子序列的

3、长度，依据该数组回溯，便可找出最长公共子序列。该算法的空间、时间复杂度均为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;ici0=0;for(i=1;ic0i=0;for(i=1;ifor(j=1;jif(xi=yj)cij=ci-1j-1+1; bij=1; else if(ci-1j=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;coutvoid lcs(int i,int j,int *x,int

4、 bn)if(i=0|j=0) return;if(bij=1)lcs(i-1,j-1,x,b);for(int y=1;yif(xy=xi)return;coutelse if(bij=2)lcs(i-1,j,x,b);elselcs(i,j-1,x,b);void quicksort(int a,int p,int r)if(pint q=partition(a,p,r);quicksort(a,p,q-1);/对左半段排序quicksort(a,q+1,r);/对右半段排序 通过动态规划求出最长公共子序列，再用任意排序算法，得出最长单调递增序列，我选用的排序方法是快速排序。 2. 一个长

5、度为i 的候选子序列的最后一个元素至少与一个长度为i-1的候选子序列的最后一个元素一样大，通过只想输入序列中元素的指针来维持候选子序列。 3. 0/1背包问题:现有n 种物品，对1动态规划算法描述: 根据问题描述，可以将其转化为如下的约束条件和目标函数：寻找一个满足约束条件，并使目标函数式达到最大的解向量，使得，而且达到最大。0-1背包问题具有最优子结构性质。假设是所给的问题的一个最优解，则是下面问题的一个最优解：。如果不是的话，设是这个问题的一个最优解，则，且。因此，这说明是所给的0-1背包问题比更优的解，从而与假设矛盾。 按照上面的情况，可以得到递推公式：设最优值为m(i,j)。 maxm

6、( i+1, j ), m( i+1, j-)+ m( i, j )= m(i+1,j)n v n j w m(n,j)= 0 0n k w #includeint 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;ivi0=0;for(j=0;jv0j=0;for(i=0;ifor(j=0;jif(jvij=vi-1j;elsevij=max(vi-1j,v

7、i-1j-wi+vi);j=c;for(i=n-1;i=0;i-)if(vijvi-1j)xi=1;j=j-wi;elsexi=0;printf(选中的物品是:n);for(i=0;iprintf(%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;iscanf(%d,&wi);printf(请分别输入物品的价值:n);for(i=0;iscanf(%d,&vi);s=knapsack(n,w,v,x,c);printf(最大物品价值为:n);printf(%dn,s);四运行结果1.2.3. 五心得体会通过这次实验，对动态规划法求最长公共子序列有更深的理解。其实无非就是抓住书上的递推公式进行写，动态规划依赖于上一个或者上一行的解，就是在输出子序列的时候有问题。自己对动态规划、贪心、回溯法、分支限界法的原理不是非常的理解，花了很多时间看了课本上的相关内容。同时课本所提供的代码也是不能直接翻译过来