湖南科技学院实验报告系部数学与计算科学专业信息与计算科学成绩评定班级信计1002班学号2010505002217姓名李游城课程名称算法设计与分析实验时间2013-04-25实验编号实验二实验名称动态规划（综合性实验）实验环境平台WindowsXP；软件CodeBlocks10.5实验目的1.理解动态规划算法的概念。2.掌握动态规划算法的基本要素。3.掌握设计动态规划算法的步骤。实验内容（①算法、程序、步骤和方法②输入、输出、实验结果③实验结果分析）1.租用游艇问题长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1≤i<j≤n。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。数据输入：由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=200），表示有n个游艇出租站。接下来的n-1行是r(i,j),1≤i<j≤n。结果输出:程序运行结束时，将输出从游艇出租站1到游艇出租站n所需的最少租金。数据文件见附件。问题分析：可知这是一个优化问题，并且具有最优子结构，表示前n-1个站的最优解，那么前n个站的最优解一定包含前n-1个站的最优解，并且它们具有重叠性。程序代码：#include<iostream>#include<sstream>#include<fstream>#include<cstdlib>usingnamespacestd;template<typenameType>voidPrint1(Type**a,intr,intc){cout<<"从第1站分别到第n站最少费用如下："<<endl;for(intj=0;j<c;j++){cout.width(4);//设置显示宽度cout<<a[1][j];}cout<<endl;cout<<"第1站到第n站最少费用="<<a[1][c-1]<<"元"<<endl;}template<typenameType>voidTwoDimArray(Type**&p,intr,intc){p=newType*[r];for(inti=0;i<r;i++)p[i]=newType[c];for(inti=0;i<r;i++)for(intj=0;j<c;j++)p[i][j]=0;}template<typenameT>voidInputData2(T**M,intr,intc,intm,char*filename)//从文件第m行开始读入一个r行c列的矩阵{ifstreaminfile;infile.open(filename);//打开文件if(!infile)//测试是否已经成功地打开了文件{cerr<<"文件打开失败！"<<endl;exit(1);//结束程序}strings;for(inti=1;i<m;i++)//读空前m-1行getline(infile,s);for(inti=1;i<r+1;++i)//读取矩阵数据{getline(infile,s);//读一行istringstreamss(s);//创建字符串流ssfor(intj=i+1;j<c+2;++j)ss>>M[i][j];//从流中读取一个T类型的数赋给M}}#include"array.h"intmain(){int**M;charfilename[]="boat1.txt";ifstreaminfile(filename);intn=0;infile>>n;TwoDimArray(M,n,n+1);InputData2(M,n-1,n-1,2,filename);for(intk=2;k<n;k++)//相隔k个站{for(inti=1;i<=n-k;i++)//计算相隔k个站的从i站到j站的最少费用{intj=i+k;for(intp=i+1;p<j;p++)//途经p站{inttmp=M[i][p]+M[p][j];if(M[i][j]>tmp)M[i][j]=tmp;}}}cout<<endl;Print1(M,n,n+1);}实验总结基本上掌握了动态规划的思想，并会利用动态规划思想解决一些简单问题。多思考，多练习，才能学好算法与设计这门课程。