Skip to content

Commit 3183957

Browse files
yanglbmeyanglbme
authored
Update MatrixChainMultiplication.java
1 parent 2da7d89 commit 3183957

File tree

1 file changed

+127
-113
lines changed

1 file changed

+127
-113
lines changed

‎Dynamic Programming/MatrixChainMultiplication.java

Lines changed: 127 additions & 113 deletions
Original file line numberDiff line numberDiff line change
@@ -1,120 +1,134 @@
11
import java.util.ArrayList;
2+
import java.util.Arrays;
23
import java.util.Scanner;
34

4-
public class MatrixChainMultiplicationTest {
5-
private static Scanner scan = new Scanner(System.in);
6-
private static ArrayList<Matrix> mArray = new ArrayList<>();
7-
private static int size;
8-
private static int[][] m;
9-
private static int[][] s;
10-
private static int[] p;
11-
12-
public static void main(String[] args) {
13-
int count = 1;
14-
while(true) {
15-
String [] mSize = input("input size of matrix A("+count+") ( ex. 10 20 ) : ");
16-
int col = Integer.parseInt(mSize[0]);
17-
if (col==0) break;
18-
int row = Integer.parseInt(mSize[1]);
19-
20-
Matrix matrix = new Matrix(count, col, row);
21-
mArray.add(matrix);
22-
count++;
23-
}
24-
for(Matrix m : mArray) {
25-
System.out.format("A(%d) = %2d x %2d\n", m.count(), m.col(), m.row());
26-
}
27-
28-
size = mArray.size();
29-
m = new int[size + 1][size + 1];
30-
s = new int[size + 1][size + 1];
31-
p = new int[size + 1];
32-
33-
for (int i=0; i<size+1; i++) {
34-
for (int j=0; j<size+1; j++) {
35-
m[i][j] = -1;
36-
s[i][j] = -1;
37-
}
38-
}
39-
40-
for (int i=0; i<p.length; i++) {
41-
if (i == 0) {
42-
p[i] = mArray.get(i).col();
43-
} else {
44-
p[i] = mArray.get(i-1).row();
45-
}
46-
}
47-
48-
matrixChainOrder();
49-
for(int i=0; i<size; i++) { System.out.print("-------"); }
50-
System.out.println();
51-
printArray(m);
52-
for(int i=0; i<size; i++) { System.out.print("-------"); }
53-
System.out.println();
54-
printArray(s);
55-
for(int i=0; i<size; i++) { System.out.print("-------"); }
56-
System.out.println();
57-
58-
System.out.println("Optimal solution : "+ m[1][size]);
59-
System.out.print("Optimal parens : ");
60-
printOptimalParens(1, size);
61-
}
62-
private static void printOptimalParens(int i, int j) {
63-
if (i == j) {
64-
System.out.print("A" + i);
65-
} else {
66-
System.out.print("(");
67-
printOptimalParens(i, s[i][j]);
68-
printOptimalParens(s[i][j] + 1, j);
69-
System.out.print(")");
70-
}
71-
}
72-
private static void printArray(int[][] array) {
73-
for (int i = 1; i < size+1; i++) {
74-
for (int j = 1; j < size+1; j++) {
75-
System.out.print(String.format("%7d", array[i][j]));
76-
}
77-
System.out.println();
78-
}
79-
}
80-
81-
private static void matrixChainOrder() {
82-
for (int i = 1; i<size+1; i++) {
83-
m[i][i] = 0;
84-
}
85-
86-
for (int l = 2; l <size+1; l++) {
87-
for (int i = 1; i<size-l+2; i++) {
88-
int j = i+l-1;
89-
m[i][j] = Integer.MAX_VALUE;
90-
91-
for (int k = i; k < j; k++) {
92-
int q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
93-
if (q < m[i][j]) {
94-
m[i][j] = q;
95-
s[i][j] = k;
96-
}
97-
}
98-
}
99-
}
100-
}
101-
102-
private static String[] input(String string) {
103-
System.out.print(string);
104-
return (scan.nextLine().split(" ") );
105-
}
5+
public class MatrixChainMultiplication {
6+
private static Scanner scan = new Scanner(System.in);
7+
private static ArrayList<Matrix> mArray = new ArrayList<>();
8+
private static int size;
9+
private static int[][] m;
10+
private static int[][] s;
11+
private static int[] p;
12+
13+
public static void main(String[] args) {
14+
int count = 1;
15+
while (true) {
16+
String[] mSize = input("input size of matrix A(" + count + ") ( ex. 10 20 ) : ");
17+
int col = Integer.parseInt(mSize[0]);
18+
if (col == 0) break;
19+
int row = Integer.parseInt(mSize[1]);
20+
21+
Matrix matrix = new Matrix(count, col, row);
22+
mArray.add(matrix);
23+
count++;
24+
}
25+
for (Matrix m : mArray) {
26+
System.out.format("A(%d) = %2d x %2d\n", m.count(), m.col(), m.row());
27+
}
28+
29+
size = mArray.size();
30+
m = new int[size + 1][size + 1];
31+
s = new int[size + 1][size + 1];
32+
p = new int[size + 1];
33+
34+
for (int i = 0; i < size + 1; i++) {
35+
Arrays.fill(m[i], -1);
36+
Arrays.fill(s[i], -1);
37+
}
38+
39+
for (int i = 0; i < p.length; i++) {
40+
p[i] = i == 0 ? mArray.get(i).col() : mArray.get(i - 1).row();
41+
}
42+
43+
matrixChainOrder();
44+
for (int i = 0; i < size; i++) {
45+
System.out.print("-------");
46+
}
47+
System.out.println();
48+
printArray(m);
49+
for (int i = 0; i < size; i++) {
50+
System.out.print("-------");
51+
}
52+
System.out.println();
53+
printArray(s);
54+
for (int i = 0; i < size; i++) {
55+
System.out.print("-------");
56+
}
57+
System.out.println();
58+
59+
System.out.println("Optimal solution : " + m[1][size]);
60+
System.out.print("Optimal parens : ");
61+
printOptimalParens(1, size);
62+
}
63+
64+
private static void printOptimalParens(int i, int j) {
65+
if (i == j) {
66+
System.out.print("A" + i);
67+
} else {
68+
System.out.print("(");
69+
printOptimalParens(i, s[i][j]);
70+
printOptimalParens(s[i][j] + 1, j);
71+
System.out.print(")");
72+
}
73+
}
74+
75+
private static void printArray(int[][] array) {
76+
for (int i = 1; i < size + 1; i++) {
77+
for (int j = 1; j < size + 1; j++) {
78+
System.out.print(String.format("%7d", array[i][j]));
79+
}
80+
System.out.println();
81+
}
82+
}
83+
84+
private static void matrixChainOrder() {
85+
for (int i = 1; i < size + 1; i++) {
86+
m[i][i] = 0;
87+
}
88+
89+
for (int l = 2; l < size + 1; l++) {
90+
for (int i = 1; i < size - l + 2; i++) {
91+
int j = i + l - 1;
92+
m[i][j] = Integer.MAX_VALUE;
93+
94+
for (int k = i; k < j; k++) {
95+
int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
96+
if (q < m[i][j]) {
97+
m[i][j] = q;
98+
s[i][j] = k;
99+
}
100+
}
101+
}
102+
}
103+
}
104+
105+
private static String[] input(String string) {
106+
System.out.print(string);
107+
return (scan.nextLine().split(" "));
108+
}
106109

107110
}
111+
108112
class Matrix {
109-
private int count;
110-
private int col;
111-
private int row;
112-
public Matrix(int count, int col, int row) {
113-
this.count = count;
114-
this.col = col;
115-
this.row = row;
116-
}
117-
public int count() { return this.count; }
118-
public int col() { return this.col; }
119-
public int row() { return this.row; }
113+
private int count;
114+
private int col;
115+
private int row;
116+
117+
Matrix(int count, int col, int row) {
118+
this.count = count;
119+
this.col = col;
120+
this.row = row;
121+
}
122+
123+
int count() {
124+
return count;
125+
}
126+
127+
int col() {
128+
return col;
129+
}
130+
131+
int row() {
132+
return row;
133+
}
120134
}

0 commit comments

Comments
 (0)