算法分析与复杂性理论实验报告动态规划教材.pdf

《算法分析与复杂性理论实验报告动态规划教材.pdf》由会员分享，可在线阅读，更多相关《算法分析与复杂性理论实验报告动态规划教材.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 深 圳 大 学 实 验 报 告 课程名称：算法分析与复杂性理论 实验名称：实验四 动态规划 学院：计算机与软件学院 专业：软件工程 报告人：文成 学号：2150230509 班级：学术型 同组人：无 指导教师：杨烜 实验时间：2015/11/52015/11/18 实验报告提交时间：2015/11/18 教务处制 一 实验目的与实验内容 实验目的：（1）掌握动态规划算法设计思想。（2）掌握背包问题的动态规划解法。实验内容：1.编写背包问题的动态规划求解代码。2背包容量为 W，物品个数为 n，随机产生 n 个物品的体积（物品的体积不可大于 W）与价值，求解该实例的最优解。3.分别针对以下情况求

2、解 第一组：（n=10,W=10），（n=10,W=20），（n=10,W=30）第二组：（n=20,W=10），（n=20,W=20），（n=20,W=30）第三组：（n=30,W=10），（n=30,W=20），（n=30,W=30）4.画出三组实验的时间效率的折线图，其中 x 轴是 W 的值，y 轴是所花费的时间，用不同的颜色表示不同 n 所花费的时间。二实验步骤与结果 背包问题的问题描述：给定 n 种物品和一个背包。物品 i 的重量是iw，其价值为iv，背包容量为 C。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？背包问题的算法思想：考虑一个由前 i 个物品（1=i=n

3、）定义的实例，物品的重量分别为 w1，w2、价值分别为 v1，vi，背包的承重量为 j（1=j=0），最优子集是由该物品和前 i-1 个物品中能够放进承重量为 j-wi 的背包的最优子集组成。这种最优子集的总价值等于 vi+Vi-1,j-wi。因此，在前 i 个物品中最优解得总价值等于这两个价值中的最大值。当然，如果第 i 个物品不能放进背包，从前 i 个物品中选出的最优子集的总价值等于从前i-1个物品中选出的最优子集的总价值。这个结果导致了下面的这个递推关系式：初始条件：当 i,j0 时，V 为了计算第 i 行第 j 列的单元格i,j，我们拿前一行同一列的单元格与vi加上前一行左边wi列的单

4、元格的和做比较，计算出两者的较大值。代码实现;/后面有个例子/说白了做法就写出最优值矩阵。void knapsack(int v,int w,int*m,int c,int n)/求最优值 int jmax=min(wn-1,c);for(int j=0;j=jmax;j+)mnj=0;for(int jj=wn;jj 1;i-)/递归部分 jmax=min(wi-1,c);for(int j=0;j=jmax;j+)mij=mi+1j;for(int jj=wi;jj=w1)m1c=max(m1c,m2c-w1+v1);cout endl 最优值：m1c endl;coutendl;cout

5、endl;int traceback(int x,int w,int*m,int c,int n)/回代，求最优解 coutendl得到的一组最优解如下:endl;for(int i=1;i n;i+)if(mic=mi+1c)xi=0;else xi=1;c-=wi;xn=(mnc)?1:0;for(int y=1;y=n;y+)cout xy t;cout 2000-3000，倍数增长，耗时 20-26-33 也成倍数增长。物品个数 N=2000 时：背包的容量 W 从：1000-2000-3000，倍数增长，耗时 24-34-48 也成倍数增长。物品个数 N=3000 时：背包的容量 W

6、 从：1000-2000-3000，倍数增长，耗时 20-40-61 也成倍数增长。结论：可以发现 当 n 固定时，花费时间随着 w 的增大而增大。n 的规模越大，所花费的时间越多。但 n 的影响力是最大的。因为动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题,采用顺序求解方法,通过解一系列小问题达到求解整个问题目的。所以分解的小问题的规模，直接决定了算法的效率。四实验心得 动态规划没有准确的数学表达式和定义精确的算法，它强调具体问题具体分析。对于一个问题是否用动态规划还是比较容易确定的，因为它是用来求最优解的，动态规划的定义虽然简单，但用起来确实另一回事。即使你知道要用动态规划却不一定真正根据题目应用好。指导教师批阅意见：成绩评定：指导教师签字：年 月 日 备注：注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。2、教师批改学生实验报告时间应在学生提交实验报告时间后 10 日内。