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:
Autoboxing và Unboxing trong Java
Java Program to Implement Suffix Array
Dockerizing a Spring Boot Application
How to Get All Spring-Managed Beans?
Java Collections Interview Questions
SOAP Web service: Upload và Download file sử dụng MTOM trong JAX-WS
Java Program to Implement the String Search Algorithm for Short Text Sizes
Java Program to Find the Minimum Element of a Rotated Sorted Array using Binary Search approach
Java Program to Check whether Undirected Graph is Connected using DFS
Java Program to Implement Ternary Search Tree
Prevent Cross-Site Scripting (XSS) in a Spring Application
Predicate trong Java 8
Java Program to Implement Direct Addressing Tables
Java Program to Perform Inorder Recursive Traversal of a Given Binary Tree
Merging Streams in Java
Java Program to Check Multiplicability of Two Matrices
Reading an HTTP Response Body as a String in Java
Build a REST API with Spring and Java Config
Serverless Functions with Spring Cloud Function
Java Program to Implement Red Black Tree
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Jackson – Decide What Fields Get Serialized/Deserialized
Spring – Injecting Collections
Overview of the java.util.concurrent
A Guide to Java HashMap
Optional trong Java 8
Error Handling for REST with Spring
A Quick Guide to Spring Cloud Consul
4 tính chất của lập trình hướng đối tượng trong Java
Java – Combine Multiple Collections
Java Program to Check Whether Graph is DAG
Java Program to Implement Gauss Jordan Elimination