GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Java/DynamicProgramming/MatrixChainMultiplication.java at master · silenceyear/Java Expand file tree/ Copy pathMatrixChainMultiplication.javaMore file actions 136 lines (115 loc) · 3.56 KB / Copy pathMatrixChainMultiplication.javaFile metadata and controls136 lines (115 loc) · 3.56 KB 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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 package DynamicProgramming; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class MatrixChainMultiplication { private static Scanner scan = new Scanner(System.in); private static ArrayList<Matrix> mArray = new ArrayList<>(); private static int size; private static int[][] m; private static int[][] s; private static int[] p; public static void main(String[] args) { int count = 1; while (true) { String[] mSize = input("input size of matrix A(" + count + ") ( ex. 10 20 ) : "); int col = Integer.parseInt(mSize[0]); if (col == 0) break; int row = Integer.parseInt(mSize[1]); Matrix matrix = new Matrix(count, col, row); mArray.add(matrix); count++; } for (Matrix m : mArray) { System.out.format("A(%d) = %2d x %2d%n", m.count(), m.col(), m.row()); } size = mArray.size(); m = new int[size + 1][size + 1]; s = new int[size + 1][size + 1]; p = new int[size + 1]; for (int i = 0; i < size + 1; i++) { Arrays.fill(m[i], -1); Arrays.fill(s[i], -1); } for (int i = 0; i < p.length; i++) { p[i] = i == 0 ? mArray.get(i).col() : mArray.get(i - 1).row(); } matrixChainOrder(); for (int i = 0; i < size; i++) { System.out.print("-------"); } System.out.println(); printArray(m); for (int i = 0; i < size; i++) { System.out.print("-------"); } System.out.println(); printArray(s); for (int i = 0; i < size; i++) { System.out.print("-------"); } System.out.println(); System.out.println("Optimal solution : " + m[1][size]); System.out.print("Optimal parens : "); printOptimalParens(1, size); } private static void printOptimalParens(int i, int j) { if (i == j) { System.out.print("A" + i); } else { System.out.print("("); printOptimalParens(i, s[i][j]); printOptimalParens(s[i][j] + 1, j); System.out.print(")"); } } private static void printArray(int[][] array) { for (int i = 1; i < size + 1; i++) { for (int j = 1; j < size + 1; j++) { System.out.print(String.format("%7d", array[i][j])); } System.out.println(); } } private static void matrixChainOrder() { for (int i = 1; i < size + 1; i++) { m[i][i] = 0; } for (int l = 2; l < size + 1; l++) { for (int i = 1; i < size - l + 2; i++) { int j = i + l - 1; m[i][j] = Integer.MAX_VALUE; for (int k = i; k < j; k++) { int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; if (q < m[i][j]) { m[i][j] = q; s[i][j] = k; } } } } } private static String[] input(String string) { System.out.print(string); return (scan.nextLine().split(" ")); } } class Matrix { private int count; private int col; private int row; Matrix(int count, int col, int row) { this.count = count; this.col = col; this.row = row; } int count() { return count; } int col() { return col; } int row() { return row; } } |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |