矩阵连乘 (Multiplying a sequence of matrices)
我们想从两个以上矩阵连乘的式子中得到最佳的次序,使得计算时乘法运算最少。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| public class DynamicProgramming {
private static final int N = 5; public static void main(String[] args) { int[][] C = new int[N][N]; int[][] S = new int[N][N]; int[] r = {4, 5, 3, 6, 4, 5}; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { C[i][j] = 0; } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { S[i][j] = 0; } } for (int p = 2; p <= N; p++) { for (int i = 0, j; i < N - p + 1; i++) { j = i + p - 1; C[i][j] = C[i][i] + C[i + 1][j] + r[i] * r[i + 1] * r[j + 1]; S[i][j] = i; for (int k = i; k< j; k++) { int temp = C[i][k] + C[k + 1][j] + r[i] * r[k + 1] * r[j + 1]; if (temp < C[i][j]) { C[i][j] = temp; S[i][j] = k; } } } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { System.out.print(C[i][j] + "\t"); } System.out.println(); } System.out.println(); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (j > i) System.out.print(S[i][j] + 1 + "\t"); else System.out.print(0 + "\t"); } System.out.println(); } } }
|