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

重庆大学实验报告实验题目：动态规划的应用学院：计算机学院专业班级：信息安全1班年级：2011级姓名：******学号：2011****完成时间：2013年6月1日指导教师：陈波重庆大学教务处制重庆大学本科学生实验项目任务书实验题目动态规划的应用学院计算机学院专业信息安全1班年级2011任务描述：有m排n列的柱桩，每一排的柱桩从左向右标号为1,2,…,n，且在每个柱桩上预先放好价值不一样的宝石。现在有位杂技演员从第一排的第1号柱桩开始跳跃，每次都必须跳到下一排的柱桩上，且每次跳跃最多只能向左或向右移动一个桩子。也就是说如果现在杂技演员站在第j号桩上，那么他可跳到下一排的第j号桩上，也可跳到下一排的第j-1(ifj1)或者j+1(ifjn)号桩上，并得到桩上的宝石。计算出一条最佳的跳跃顺序，使杂技演员获得的宝石的总价值最大。（输入）44（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，测试数据均在同一目录中，在任意一台WinXP机器上直接双击exe即可运行。2.测试数据不少于20排20列，按照前述的格式放在test.txt文件里，执行结果存入output.txt文件里参考资料：AlgorithmDesign,JonKleiberg.EvaTardos,CornellUniversity任务下达日期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(inti=1;i=row;i++)maxb[line][i]=gem[line][i];//初始化maxbfor(inti=line-1;i=1;i--)for(intj=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[]，然后再判断该最大值的下排与之相邻的三个maxb值，而后重复上面的操作，直到最后一排。求path的伪代码如下：path[1]=1//因为每次都是从第一排的第一桩开始，所以，path[1]=1n=1;for(inti=2;i=line;i++)max{maxb[i][n-1],maxb[i][n],maxb[i][n+1]}path[i]=n;//如果maxb[i][n]最大，则n=n-1;由该代码可知，求path的时间复杂度为O(n)。2关键代码描述#includeiostream#includefstreamusingnamespacestd;voidmain(){ofstreamoutfile;//实验结果读入outfile文件中ifstreaminfile;//实验数据从infile文件中读入outfile.open(output.txt,ios::trunc);infile.open(test.txt,ios::in);if(infile==NULL)cout文件内没有内容！;intline,row;infileline;infilerow;int**gem;int**maxb;//数组gem表示柱桩的宝石，数组maxb表示第i行第j列到最后一行所获得的最大宝石数；intnum=abs(line-row);gem=(int**)newint*[line+num+1];maxb=(int**)newint*[line+num+1];//动态为数组gem和maxb分配空间for(inti=0;i=line;i++){gem[i]=newint[row+num+1];maxb[i]=newint[row+num+1];}for(inti=1;i=line;i++)for(intj=1;j=row;j++)infilegem[i][j];//输入柱桩的宝石for(inti=1;i=row;i++)maxb[line][i]=gem[line][i];//初始化maxb/*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从line取到1*/for(inti=line;i1;i--)for(intj=row;j=1;j--){intn=i-1;if((gem[n][j]+maxb[i][j-1])=(gem[n][j]+maxb[i][j])&&(gem[n][j]+maxb[i][j-1])=(gem[n][j]+maxb[i][j+1])){maxb[n][j]=gem[n][j]+maxb[i][j-1];continue;}if((gem[n][j]+maxb[i][j])=(gem[n][j]+maxb[i][j-1])&&(gem[n][j]+maxb[i][j])=(gem[n][j]+maxb[i][j+1])){maxb[n][j]=gem[n][j]+maxb[i][j];continue;}if((gem[n][j]+maxb[i][j+1])=(gem[n][j]+maxb[i][j-1])&&(gem[n][j]+maxb[i][j+1])=(gem[n][j]+maxb[i][j])){maxb[n][j]=gem[n][j]+maxb[i][j+1];continue;}}outfilemaxb[1][1](最大价值)\n;int*path,n=1;//数组path用来记录获得最多宝石数时，经过每排的位置path=newint[line+num+1];path[1]=1;//因为每次都是从第一排的第一桩开始，所以，path【1】=1/*从上往下找出每排p取得最大值得位置，存入数组s中*/for(inti=1;iline;i++){intm=i+1;if((maxb[m][n-1]=maxb[m][n])&&(maxb[m][n-1]=maxb[m][n+1])){path[m]=n-1;n=n-1;continue;}if((maxb[m][n]=maxb[m][n-1])&&(maxb[m][n]=maxb[m][n+1])){path[m]=n;n=n;continue;}if((maxb[m][n+1]=maxb[m][n])&&(maxb[m][n+1]=maxb[m][n-1])){path[m]=n+1;n=n+1;continue;}}cout打开output文件查看结果！endl;for(inti=1;i=line;i++)outfilepath[i](第i排位置)\n;for(inti=0;i=line;i++)delete[]gem[i];delete[]gem;for(inti=0;i=line;i++)delete[]maxb[i];delete[]maxb;deletepath;outfile.close();infile.close();}3运行效果/*test.txt内的内容*/24201111111111111111111115112314532122122111112130132112435412222111126201111134554321112312311223123456789075331453420976543216438732564896894466357433345784511463626384532345678912634684287645252345678111632252511111555555551111111111114444444411111111111177777777222222211111188888888333332222221132244242563468428764525234567811163225251111155555555111111111111444444441111111111117777777722222221111118888888833333222222113224424250976543216438732564896894466357433345784511463626384532345678912634684287645252345678111/*output.txt内的内容*/345(最大价值)1(第1排位置)2(第2排位置)3(第3排位置)4(第4排位置)5(第5排位置)6(第6排位置)7(第7排位置)8(第8排位置)9(第9排位置)8(第10排位置)7(第11排位置)6(第12排位置)7(第13排位置)8(第14排位置)9(第15排位置)10(第16排位置)11(第17排位置)12(第18排位置)13(第19排位置)14(第20排位置)13(第21排位置)14(第22排位置)15(第23排位置)16(第24排位置)4总结(注明每个人的分工和工作量百分比)本组由2011****组成。2011****负责项目的所有部分，所作贡献占工作量的100%。格式要求纸张大小：A4页边距：上下左右各留20mm行距：采用固定值20磅标题：章节标题使用三号黑体、居中（大标题使用四号黑体，小标题使用小四号黑体）正文：小四号宋体页眉：“学生姓名：课程设计题目”，五号宋体，居中页脚：阿拉伯数字编页码，小五号宋体，居中参考文献：五号宋体附录：五号宋体备注：1、学生：提交的实验报告电子文档命名为：“组号（2位数字）年级（两位数字不要“级”字）专业（缩写：计算机科学与技术专业（计科）、网络工程专业（网络）、信息安全专业（信息）、物联网工程（物联网））项目组成员（学号（八位数字）姓名）．doc。如第1组，专业为“计算机科学与技术”专业，项目组成员有：张三（学号20115676），李四（学号20115676），王五（学号20115676），完成的课程设计报告命名为：01_10计科_20115676张三_20115676李四_20115676王五。2、教师：报告批阅完成后将评价后的实验报告转换为PDF格式文件刻光盘，连同实验成绩单一起放入试卷袋存档。