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:
The Registration API becomes RESTful
Hướng dẫn sử dụng String Format trong Java
Spring Boot - Interceptor
Introduction to Spliterator in Java
Giới thiệu Design Patterns
Java Program to Check the Connectivity of Graph Using DFS
So sánh HashSet, LinkedHashSet và TreeSet trong Java
Tìm hiểu về Web Service
Java Program to Find Whether a Path Exists Between 2 Given Nodes
HashSet trong Java hoạt động như thế nào?
Java Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range
Check if there is mail waiting
Jackson Date
Java Program to Implement RoleUnresolvedList API
Java Program to Perform Partition of an Integer in All Possible Ways
Java Program to Implement Hash Tables Chaining with List Heads
Java Program to Implement Stein GCD Algorithm
Java Program to Check if an UnDirected Graph is a Tree or Not Using DFS
How to Read a Large File Efficiently with Java
Programmatic Transaction Management in Spring
Generic Constructors in Java
Java Program to Implement Warshall Algorithm
Java Program to Sort an Array of 10 Elements Using Heap Sort Algorithm
Java Program to Solve TSP Using Minimum Spanning Trees
Entity To DTO Conversion for a Spring REST API
Spring Data JPA @Modifying Annotation
Spring Security Remember Me
String Joiner trong Java 8
Prevent Cross-Site Scripting (XSS) in a Spring Application
Java Program to Find the Connected Components of an UnDirected Graph
Logout in an OAuth Secured Application
Java Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity