l算法分析动态规划实验报告.docVIP

重庆大学实验报告 实验题目： 动态规划的应用 学 院： 计算机学院 专业班级： 信息安全1班 年 级： 2011级 姓 名： ****** 学 号： 2011**** 完成时间： 2013 年 6 月 1 日 指导教师： 陈 波 重庆大学教务处制 重庆大学本科学生实验项目任务书 实验题目 动态规划的应用 学院 计算机学院 信息安全1班 年级 2011 任务描述： 有m排n列的柱桩，每一排的柱桩从左向右标号为1,2,…,n，且在每个柱桩上预先放好价值不一样的宝石。现在有位杂技演员从第一排的第1号柱桩开始跳跃，每次都必须跳到下一排的柱桩上，且每次跳跃最多只能向左或向右移动一个桩子。也就是说如果现在杂技演员站在第j号桩上，那么他可跳到下一排的第j号桩上，也可跳到下一排的第j-1 (if j1)或者 j+1 (if jn) 号桩上，并得到桩上的宝石。计算出一条最佳的跳跃顺序，使杂技演员获得的宝石的总价值最大。 （输入）4 4 （4排4列的柱桩，空格隔开）1,1, 1, 1 （放在第1排各桩上的宝石价值，逗号隔开）1, 5, 1, 1 。2 ,1, 10, 1 。20 ,1, 1, 1 （放在第4排各桩上的宝石价值） （输出）28 （最大价值）1 (开始位置，固定)2 (在第二排的位置)1 (在第三排的位置)1 (在第四排的位置) 设计要求： a.单人独立完成；b.提交名为 学号__PJ.rar 的压缩文件，含如下内容：1). 完整的源码 2).不依赖于IDE环境的可执行文件及测试数据 3).电子版本项目报告，报告中至少包括对算法思想、递推方程式及该问题的最优子结构性质、程序结构的描述以及计算复杂度分析, 以及测试结果c. 第15周周五之前交，请直接提交至SAKAI。说明：1. 不依赖于IDE环境的可执行文件指exe及其支持dll，测试数据均在同一目录中，在任意一台Win XP机器上直接双击exe即可运行。2. 测试数据不少于20排20列，按照前述的格式放在test.txt文件里，执行结果存入output.txt文件里 参考资料： Algorithm Design, Jon Kleiberg. Eva Tardos, Cornell University 任务下达日期 2013 年 5月 26 日 完成日期2013年 6 月 1 日 说明：学院、专业、年级均填全称，如：计算机学院、计算机科学与技术、2011。 实验报告正文 主要内容包括： 1 算法思想 (a), 使用动态规划自下而上方法，定义数组gem[i][j]表示第i排第j列木桩上的宝石数，数组maxb[i][j]表示从第i排第j列木桩到最后一排木桩所获得的最大宝石数。公式为： maxb[i][j]=max{gem[i][j]+maxb[i+1][j-1],gem[i][j]+maxb[i+1][j], gem[i][j]+maxb[i+1][j+1] }其中i从n取到1 求maxb的伪代码如下： Dynamic-Bottom-To-Up(maxb,gem,row,line) for(int i=1;i=row;i++) maxb[line][i]=gem[line][i]; //初始化maxb for(int i=line-1;i=1;i--) for(int j=row;j=1;j--) maxb[i][j]=max{gem[i][j]+maxb[i+1][j-1],gem[i][j]+maxb[i+1][j], gem[i][j]+maxb[i+1][j+1] } 由上述代码可知，最多两个for循环，所以，时间复杂度为O(n2). (b), 用数组path[]记录获得最大价值的路径，思想是自上而下比较每排的maxb最大值，将位置赋给数组path[]，然后