java实验-设计动态规划算法

Question

设平面上有一个m×n 的网格，将左下角的网格点标记为（0,0）而右上角的网格点标记为（m,n）。某人想从（0,0）出发沿网格线行进到达（m,n），但是在网格点（i,j）处他只能向上行进或者向右行进，向上行进的代价为aij（amj ＝＋∞），向右行进的代价是bij（bin ＝＋∞）。试设计一个动态规划算法，在这个网格中为该旅行者寻找一条代价最小的旅行路线。

Answer 1

import java.util.*;

import static java.lang.Math.*;

public class Shiyaner

{

public static void main(String[] args)

{

final int m = 5;

final int n = 5;

// 定义向上，向右的代价，以及最优代价

int[][] Cost = new int[m+1][n+1];

int[][] Down = new int[m][n+1];

int[][] Right = new int[m+1][n];

int count = 0, i = 0, j = 0;

// 随机的产生向上代价数组Above，并输出

for(i = 0; i < m; i++)

for(j = 0; j < n+1; j++)

{

Random rand = new Random();

Down[i][j] = (rand.nextInt(5)+5);

}

System.out.printf("Down:\n");

for(i = 0; i < m; i++)

{

for(j = 0; j < n+1; j++)

{

System.out.printf("%5d", Down[i][j]);

}

System.out.println("\n");

}

// 随机的产生向右代价数组Right，并输出

for(i = 0; i < m+1; i++)

for(j = 0; j < n; j++)

{

Random rand = new Random();

Right[i][j] = (rand.nextInt(5)+5);

}

System.out.printf("Right:\n");

for(i = 0; i < m+1; i++)

{

for(j = 0; j < n; j++)

{

System.out.printf("%5d", Right[i][j]);

}

System.out.println("\n");

}

// 求出最优代价数组Cost并输出

Cost[0][0] = 0;

for(i = 1; i < m+1; i++)

Cost[i][0] = Cost[i-1][0] + Down[i-1][0];

for(j = 1; j < n+1; j++)

Cost[0][j] = Cost[0][j-1] + Right[0][j-1];

for(i = 0; i < m; i++)

for(j = 0; j < n; j++)

Cost[i+1][j+1] = min((Cost[i+1][j] + Right[i+1][j]), (Cost[i][j+1] +

Down[i][j+1]));

System.out.printf("最优距离:\n");

for(i = 0; i < m+1; i++)

{

for(j = 0; j < n+1; j++)

{

System.out.printf("%5d",Cost[i][j]);

}

System.out.println("\n");

}

// 输出最优路径的具体走法

System.out.println("请输入你想到达的坐标位置：");

Scanner in1 = new Scanner(System.in);

System.out.print("横坐标：");

int a = in1.nextInt();

System.out.print("纵坐标：");

int b = in1.nextInt();

int[] d = new int[a+b];

int k = a+b-1;

i = a - 1 ;

j = b - 1 ;

while ( i != 0 && j != 0 )

{

if ( Cost[i+1][j+1] == (Cost[i+1][j] + Right[i+1][j]))

{

d[k] = 0;

j--;

k--;

}

else

{

d[k] = 1;

i--;

k--;

}

}

if( i == 0 )

{

while ( j != 0 )

{

d[k] = 1;

j--;

k--;

}

}

if( j == 0 )

{

while ( i != 0 )

{

d[k] = 0;

i--;

k--;

}

}

for (i = a+b-1 ; i >= 0 ; i-- )

{

if ( d[i] == 0 )

System.out.println("Right");

else

System.out.println("Down");

}

}

}

运行结果如下：

Down:

5 9 7 6 5 6

8 9 8 5 7 6

9 6 7 9 6 5

9 9 7 5 6 6

5 7 5 9 5 5

Right:

7 7 9 8 8

6 6 5 6 6

8 9 7 9 8

9 7 7 5 8

6 7 7 9 7

6 7 8 5 6

最优距离:

0 7 14 23 31 39

5 11 17 22 28 34

13 20 25 27 35 40

22 26 32 36 41 45

31 35 39 41 47 51

36 42 44 50 52 56

请输入你想到达的坐标位置：

横坐标：3

纵坐标：3

Down

Down

Down

Down

Right

Right