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:
Spring RestTemplate Request/Response Logging
Java Program to Implement Bresenham Line Algorithm
Java Program to Implement Gabow Algorithm
Java Program to Implement Hash Tables
Lớp Arrarys trong Java (Arrays Utility Class)
Java Program to Implement Unrolled Linked List
Java Program to Implement Euclid GCD Algorithm
Concatenating Strings In Java
Tính đa hình (Polymorphism) trong Java
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Java Program to Implement Borwein Algorithm
LinkedHashSet trong Java hoạt động như thế nào?
A Guide to Java HashMap
Spring Boot - Application Properties
Java Program to Implement Find all Forward Edges in a Graph
Java Program to Generate a Sequence of N Characters for a Given Specific Case
Java Program to Perform Search in a BST
Java Program to Find the Minimum value of Binary Search Tree
Converting between an Array and a List in Java
Java Program to Perform Searching Based on Locality of Reference
Spring Boot - Rest Controller Unit Test
Java Program to Find a Good Feedback Edge Set in a Graph
Guava – Join and Split Collections
File Upload with Spring MVC
Getting a File’s Mime Type in Java
Java Program to Implement Ternary Search Tree
Check If a File or Directory Exists in Java
Java Program to find the number of occurrences of a given number using Binary Search approach
Cài đặt và sử dụng Swagger UI
Spring Boot Tutorial – Bootstrap a Simple Application
Spring Security OAuth2 – Simple Token Revocation
Adding Shutdown Hooks for JVM Applications