Java/DynamicProgramming/MatrixChainMultiplication.java at master · geran/Java · GitHub

History

136 lines (115 loc) · 3.56 KB

Raw

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;

}

Java/DynamicProgramming/MatrixChainMultiplication.java at master · geran/Java · GitHub

Expand file tree

Breadcrumbs

MatrixChainMultiplication.java

Latest commit

History

Breadcrumbs

MatrixChainMultiplication.java

File metadata and controls