租用游艇问题

租用游艇问题1.问题描述长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r（i，j），1≤ij≤n。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。算法设计：对于给定的游艇出租站i对游艇出租站j之间的租金为r（i，j），1≤ij≤n，计算从游艇出租站1到游艇出租站n所需的最少租金。2.算法流程分析设游艇出租站有N个，而且每两个站的租金都是不一样的，用f（i，j）表示每两个站之间的租金费用。当要租用游艇从一个站到另外一个站时，采取不同的停靠站策略就有不同的租金。例如输入3,5,15,7，,那么从第一个站到第三个站，租金是15元，但是第一个站到第二个站的租金只需5元，第二到第三个站的租金要7元，因此可采用先到第二个站，把游艇归还，然后再从第二个站租用游艇到第三个站，因此我们总共需要的费用就是5+7=12元，比直接从第一个站到第三个站要花15元更经济，也就是最少花费。这是一个优化问题，并且具有最优子结构，表示前n-1个站的最优解，那么前n个站的最优解一定包含前n-1个站的最优解，并且它们具有重叠性。3.算法正确性证明通过几组实例证明合法的输入可以得到正确的输出。实例见附录第2部分。4.算法复杂度分析O（n^3）5.参考文献[1]王晓东编著，计算机算法设计与分析（第4版）。北京：电子工业出版社，2012.26.附录（1）可执行代码如下：#includeiostreamusingnamespacestd;intw[200],z[200][200],n;intsolve(inth){if(w[h]0)returnw[h];if(h==n-1)returnz[h][n];intminn=z[h][n];for(intk=h+1;kn;k++){inta=z[h][k]+solve(k);if(aminn)minn=a;}w[h]=minn;returnminn;}intmain(){inti,j;cout请输入游艇出租站的个数：endl;cinn;for(i=1;in;i++)for(j=i+1;j=n;j++){cout请输入从i站到j站的租金：endl;cinz[i][j];}cout从游艇出租站1到游艇出租站n所需的最少租金：endlsolve(1)endl;return0;}（2）输入输出实例输入35157输出如下：12