当前位置: 首页 > >

游船费问题-动态规划

发布时间:

问题描述

某旅游城市在长江边开辟了若干个旅游景点。一个游船俱乐部在这些景点都设置了游船出租站,游客可在这些游船出租站租用游船,并在下游的任何一个游船出租站归还游船,从一个游船出租站到下游的游船出租站间的租金明码标价的。你的任务是为游客计算从起点站到终点站间的最少租船费用。


输入

输入有若干组测试数据,每组测试数据的第一行上有一个整数n,(1<=n<=100),表示上游的起点站0到下游有n个游船出租站1、2、…、n。接下来有n行,这n行中的第1行有n个整数,分别表示第0站到第1、2、3、…、n站间的游船租金;第2行有n-1个整数,分别表示第1站到第2、3、4、…、n站间的游船租金;…;第n-1行有2个整数,表示第n-2站到第n-1、n站间的游船租金;第n行有1个整数,表示第n-1站到第n站间的游船租金。一行上两个整数之间是用空格隔开的。当游船租金是-1时,表示这两个站之间无直通航线。两组测试数据之间无空行。


输出

对输入中描述的每组测试数据,先在一行上输出“Case #:”,其中“#”测试数据的编号(从1开始编)。对输入文件中的每组测试数据,在输出文件中输出一行,内容是该情况下游客从起点站到终点站间的最少租船费用。


输入样例

3
2 3 6
1 3
2
3
4 7 9
4 5
6


输出样例

Case 1:
5
Case 2:
9


算法思路

用r[i][j]记录第i站到第j站的直达游船租金,f[i]记录从起点第0站到第i站的最少游船租金。那么从第0站到第i站有两种方式到达:


直达:r[0][i]中转:在第k站进行中转,从第0站到第k站最少租金f[k],从第k站到第i站直达租金r[k][i]
则求解的从第0站到第i站的最少租金为:





f


(


i


)


=



{







m


i



n



0


<


k


<


i




(


f


[


k


]


+


r


[


k


]


[


i


]


,


r


[


0


]


[


i


]


)








i


>


0










r


[


0


]


[


i


]








i


=


0









f(i)=egin{cases} min_{00 \ r[0][i ]& i=0 end{cases}


f(i)={min00i=0?

从起点(第0站开始),首先计算到第1站的最优值f(1),因为没有中转站,所以可以直接得到。计算起点到第2站的时候,就要取直达和经第1站中转的最小值。计算起点到第3站的时候,就要取直达和经第1站中转、经第2站中转的最小值。以此类推,直到求解出f[n],即起点到终点的费用。这样先解决了子问题,然后逐步求出了待求解问题。


代码实现

public class Main {

//上游的起点站0到下游有n个游船出租站
private static int n;

// r[i][j]表示从i直达j+1站的租金
private static int[][] r;

// f[i]表示从0到i站的最少租金
private static int[] f;

public static void main(String[] args) {
// 读取键盘输入
Scanner sc = new Scanner(System.in);
int count = 0;
while (true) {
count++;
n = sc.nextInt();
r = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
r[i][j] = sc.nextInt();
}
}
System.out.println("Case " + count + ":
" + solution() + "
");
}
}

public static int solution() {
// f[0]=0,f[n]表示起点到终点
f = new int[n + 1];
// 从1到n的最少费用,求n要用到n-1,求n-1...
for (int i = 1; i <= n; i++) {
// 0到i直达
f[i] = r[0][i - 1];
for (int k = i - 1; k > 0; k--) {
// 0到i直达或者经过k中转
f[i] = min(f[i], f[k] + r[k][i - 1]);
}
}
return f[n];
}
}



友情链接: