动态规划算法—租用游艇问题.docxVIP

动态规划算法——租用游艇问题

（一）实验目的：

理解动态规划思想，掌握用动态规划设计算法的方法来解决游艇租用问题。

（二）实验内容：

长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r（i,j）.设计一个算法，计算出从游艇出租站1到游艇出租站n所需要的最少租金。

（三）实验要求：

对于给定的游艇出租站i到游艇出租站j之间的租金为r（i,j），编程计算从游艇出租站1到游艇出租站n所需要的最少租金。上机调试并测试，记录调试和测试的情况，结合程序进行分析。

（四）实验环境：

Vc++编译环境

（五）实验主要源代码：

（1）用dyna（）函数计算最少租金voiddyna(intn,intf[N][N]){

for(intk=2;kn;k++)for(inti=0;in-k;i++){

intj=i+k;

for(intp=i+1;pj;p++){

inttmp=f[i][p]+f[p][j];if(f[i][j]tmp)

f[i][j]=tmp;

}

}

}

（2）在主函数中实现输出结果。

intmain()

{

ifstreamfin(050501103in.txt);ofstreamfout(050501103out.txt);if(fin.fail()){

coutfin(\050501103in.txt\)文件出错！请先建立050501103in文本！

endl;

return1;

}

if(fout.fail()){

coutfout(\050501103out.txt\)文件出错！;return2;

}

intf[N][N];intn;

inti,j;finn;if(n=0)

{cout请在050501103in文本的第一行中输入游艇出租站的个数：endl;

cout请在050501103in文本的第二行开始输入n（n-1）/2个站与站之间的租金数：endl;}

elseif(nN){

cout请修改N的值,使N大于n：endl;}else{

for(i=0;in;i++)for(j=0;jn;j++)

if(ji)

finf[i][j];

cout请在050501103out文本中看输出结果（从出租站1到n的最少租金）：endl;

dyna(n,f);foutf[0][n-1]endl;

}

}

（六）实验结果：

050501103in.txt 050501103out.txt3 12

515

7

（七）实验总结：

此程序的设计思想：利用dyna（）函数计算最少租金。然后在主函数中实现输出结果，思路比较清晰。

遇到的问题：在编写程序的过程中也遇到了一些问题。1、编译之前创建了一个空的输入文本，但在运行时出现应用程序错误。于是，在输入数时，加了一

个条件语句if(n=0，)问题得到了解决。2、为了使程序更为完善，我又加了一

条语句，提示用户适时的修改N的值。3、开始是不知道二维数组如何输入，多次测试后，找到了方法。

总结：多次程序编译下来，感觉自己收获了很多。基本的错误也越来越少。能够在提示下，独立修改自己的错误。