Please write the following program in C++: Instructions: Matrix Chain Algorithm:
ID: 3805183 • Letter: P
Question
Please write the following program in C++:
Instructions:
Matrix Chain Algorithm:
Dynamic Programming: Matrix Chain Multiplication Description this assignment you are asked to implement a dynamic programming algo- rithm: matrix chain multiplication (chapter 15.2), where the goal is to find the most computa- tionally efficient matrix order when multiplying an arbitrary number of matrices in a row. You can assume that the entire input will be given as integers that can be stored using the standard C++ int type and that matrix sizes will be at least 1 Input The input has the following format. The first number, n 1, in the test case will tell you how many matrices are in the sequence. The first number will be then followed by n 1 numbers indicating the size of the dimensions of the matrices. Recall that the given information is enough to fully specify the dimensions of the matrices to be multiplied. Output First, you need to output the minimum number of scalar multiplications needed to multiply the given matrices. Then, print the matrix multiplication sequence, via parentheses that minimizes the total number of mumber multiplications. Each matrix should be named A#, where is the matrix number starting at 0 (zero) and ending at n 1. See the examples below Examples of input and output 2 3 5 30 (A0A1) 10 100 5 50 7500 C (A0A1)A2) 10 30 5 60 4500 C (A0A1)A2) 30 35 15 5 10 20 25 15125 ((A0 (A1A2) (A3A4) A5))Explanation / Answer
// C++ program to print optimal parenthesization
// in matrix chain multiplication.
#include<bits/stdc++.h>
using namespace std;
// Function for printing the optimal
// parenthesization of a matrix chain product
void printParenthesis(int i, int j, int n,
int *bracket, char &name)
{
// If only one matrix left in current segment
if (i == j)
{
cout << "A" <<name++;
return;
}
cout << "(";
// Recursively put brackets around subexpression
// from i to bracket[i][j].
// Note that "*((bracket+i*n)+j)" is similar to
// bracket[i][j]
printParenthesis(i, *((bracket+i*n)+j), n,
bracket, name);
// Recursively put brackets around subexpression
// from bracket[i][j] + 1 to j.
printParenthesis(*((bracket+i*n)+j) + 1, j,
n, bracket, name);
cout << ")";
}
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
// Please refer below article for details of this
// function
// https://goo.gl/k6EYKj
void matrixChainOrder(int p[], int n)
{
/* For simplicity of the program, one extra
row and one extra column are allocated in
m[][]. 0th row and 0th column of m[][]
are not used */
int m[n][n];
// bracket[i][j] stores optimal break point in
// subexpression from i to j.
int bracket[n][n];
/* m[i,j] = Minimum number of scalar multiplications
needed to compute the matrix A[i]A[i+1]...A[j] =
A[i..j] where dimension of A[i] is p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for (int i=1; i<n; i++)
m[i][i] = 0;
// L is chain length.
for (int L=2; L<n; L++)
{
for (int i=1; i<n-L+1; i++)
{
int j = i+L-1;
m[i][j] = INT_MAX;
for (int k=i; k<=j-1; k++)
{
// q = cost/scalar multiplications
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;
// Each entry bracket[i,j]=k shows
// where to split the product arr
// i,i+1....j for the minimum cost.
bracket[i][j] = k;
}
}
}
}
// The first matrix is printed as 'A', next as 'B',
// and so on
char name = '0';
cout << "Optimal Parenthesization is : ";
printParenthesis(1, n-1, n, (int *)bracket, name);
cout << " Optimal Cost is : " << m[1][n-1];
}
// Driver code
int main()
{
int m;
cin >> m;
while(m--)
{
int n;
cin >>n;
n = n+1;
int arr[n];
for(int i = 0; i < n; i++)
cin >> arr[i];
matrixChainOrder(arr, n);
cout << endl;
}
return 0;
}
// sample input
4
2
2 3 5
3
10 100 5 50
3
10 30 5 60
6
30 35 15 5 10 20 25
// sample output