This is a java program to perform optimal paranthesization by making use of dymanic programming. This program determines the order in which the chain of matrices should be multiplied.
Here is the source code of the Java Program to Perform Optimal Paranthesization Using Dynamic Programming. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
package com.sanfoundry.numerical; import java.util.Scanner; public class OptimalParanthesizationUsingDP { private int[][] m; private int[][] s; private int n; public OptimalParanthesizationUsingDP(int[] p) { n = p.length - 1; // how many matrices are in the chain m = new int[n + 1][n + 1]; // overallocate m, so that we don't use index // 0 s = new int[n + 1][n + 1]; // same for s matrixChainOrder(p); // run the dynamic-programming algorithm } private void matrixChainOrder(int[] p) { // Initial the cost for the empty subproblems. for (int i = 1; i <= n; i++) m[i][i] = 0; // Solve for chains of increasing length l. for (int l = 2; l <= n; l++) { for (int i = 1; i <= n - l + 1; i++) { int j = i + l - 1; m[i][j] = Integer.MAX_VALUE; // Check each possible split to see if it's better // than all seen so far. 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]) { // q is the best split for this subproblem so far. m[i][j] = q; s[i][j] = k; } } } } } private String printOptimalParens(int i, int j) { if (i == j) return "A[" + i + "]"; else return "(" + printOptimalParens(i, s[i][j]) + printOptimalParens(s[i][j] + 1, j) + ")"; } public String toString() { return printOptimalParens(1, n); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out .println("Enter the array p[], which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]"); System.out.println("Enter the total length: "); int n = sc.nextInt(); int arr[] = new int[n]; System.out.println("Enter the dimensions: "); for (int i = 0; i < n; i++) arr[i] = sc.nextInt(); OptimalParanthesizationUsingDP opudp = new OptimalParanthesizationUsingDP( arr); System.out.println("Matrices are of order: "); for (int i = 1; i < arr.length; i++) { System.out.println("A" + i + "-->" + arr[i - 1] + "x" + arr[i]); } System.out.println(opudp.toString()); sc.close(); } }
Output:
$ javac OptimalParanthesizationUsingDP.java $ java OptimalParanthesizationUsingDP Enter the array p[], which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i] Enter the total length: 5 Enter the dimensions: 2 4 5 2 1 Matrices are of order: A1-->2x4 A2-->4x5 A3-->5x2 A4-->2x1 (A[1](A[2](A[3]A[4])))
Related posts:
HashMap trong Java hoạt động như thế nào?
Java Program to Implement Gabow Algorithm
Guide to the Fork/Join Framework in Java
Java Collections Interview Questions
An Intro to Spring Cloud Vault
Introduction to Spring Data JPA
Allow user:password in URL
Java Program to Implement Dijkstra’s Algorithm using Priority Queue
Java Program to Construct an Expression Tree for an Postfix Expression
Java Program to Search Number Using Divide and Conquer with the Aid of Fibonacci Numbers
Removing all Nulls from a List in Java
Life Cycle of a Thread in Java
A Guide to @RepeatedTest in Junit 5
Dockerizing a Spring Boot Application
Spring MVC Setup with Kotlin
Spring Boot Configuration with Jasypt
Optional trong Java 8
Multi Dimensional ArrayList in Java
Spring MVC Custom Validation
SOAP Web service: Authentication trong JAX-WS
Request Method Not Supported (405) in Spring
Java 9 Stream API Improvements
Java – Create a File
Java Program to Implement LinkedBlockingDeque API
Rate Limiting in Spring Cloud Netflix Zuul
Java Program to Check if a Given Binary Tree is an AVL Tree or Not
Java Program to Compute the Area of a Triangle Using Determinants
Java Program to Implement Adjacency List
Hamcrest Collections Cookbook
Guava Collections Cookbook
Java Program to Find Basis and Dimension of a Matrix
Inheritance and Composition (Is-a vs Has-a relationship) in Java