Algorithm dynamic programming!! Help thanks Dynamic Programming: Optimal Matrix

Question

Algorithm dynamic programming!! Help thanks

Dynamic Programming: Optimal Matrix Chain Multipli- cation Order In this assignment you are asked to implement a dynamic programming algorithm: matrix chain multiplication (chapter 15.2), where the goal is to find the most computationally efficient matrix order when multiplying an arbitrary number of matrices in a row. You can assume that the that matrix sizes will be at least 1. You will use "Grade06" to grade your code. Your execution file name must be "MatrixChain.exe". Refer to the previous lab assignments for instructions on how to use the grading tool. 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 n1 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. First, you need to output the minimu number of scalar multiplications needed to multiply the given matrices. Then, print the matrix multiplication sequence, via parentheses, that minimizes the total number of 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

Explanation / Answer

// C++ program to print optimal parenthesization

// in matrix chain multiplication. and i am giving output formate as your .

#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,int& num)

{

// If only one matrix left in current segment

if (i == j)

{

cout << name<<num++;

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,num);

// Recursively put brackets around subexpression

// from bracket[i][j] + 1 to j.

printParenthesis(*((bracket+i*n)+j) + 1, j,

n, bracket, name,num);

cout << ")";

}

// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n

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 = 'A';

int num=0;

cout<<m[1][n-1]<<endl;

printParenthesis(1, n-1, n, (int *)bracket, name,num);

}

// Driver code

int main()

{

int n; //number of test case

  

cin>>n;

for(int j=1;j<=n;j++)

{

int N; //Number of matrix

cin>>N;

int arr[N+1];

for(int i=0;i<=N;i++)

{

cin>>arr[i];

}

cout<<"Output "<<j<<endl; // j is test case

matrixChainOrder(arr, N+1);

cout<<endl;

}

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.