java游艇问题,租用游艇问题——Java实现

java游艇问题,租用游艇问题——Java实现

1. 问题描述

长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1£i

2. 编程任务

出租站i到游艇出租站j之间的租金为r(i,j),1≤i

3. 问题分析

仍然使用租金数组 r(i, j)(1≤i

依照上述写出算法的递归式如下：

4. 代码实现

下面是关键类CalculateRent的实现代码，测试代码就不贴了，因为涉及到文件读写和数组 r[][] 的初始化。

public class CalculateRent {

private int[][] r;

public CalculatePay(int r[][]){

this.r = r;

}

public int[][] calculate(){

int n = r[0].length;

//计算第 i 个站到第 j 个站的最少租金

for (int i = 0; i <= n-1; i++) {//i 代表起始站

for (int j = i+2; j <= n-1; j++) {// j代表终点站

for (int k = i+1; k <=j-1 ; k++) {//k 代表途径站

int m = r[i][k] + r[k][j];//记录下经过 k 站时的租金

if (m

r[i][j] = m;//则把更便宜的值记录下来

}

}

}

return r;

}

}