Untitled
unknown
plain_text
6 months ago
2.5 kB
1
Indexable
Never
#include <iostream> #include <vector> #include <climits> // Function to print the optimal parenthesized sequence order void printParenthesis(int i, int j, std::vector<std::vector<int>>& bracket, char& name) { // Base case: when there is only one matrix in the chain if (i == j) { std::cout << name++; return; } std::cout << "("; // Recursively print optimal parenthesized sequence order // for matrices from i to bracket[i][j] printParenthesis(i, bracket[i][j], bracket, name); // Recursively print optimal parenthesized sequence order // for matrices from bracket[i][j] + 1 to j printParenthesis(bracket[i][j] + 1, j, bracket, name); std::cout << ")"; } // Function to find the minimum cost required to multiply the matrices int matrixChainOrder(std::vector<int>& dims) { int n = dims.size() - 1; // number of matrices // Create matrices to store the minimum cost and optimal // parenthesized sequence order std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0)); std::vector<std::vector<int>> bracket(n, std::vector<int>(n, 0)); // Compute minimum cost for all chain lengths from 2 to n for (int len = 2; len <= n; ++len) { for (int i = 0; i <= n - len; ++i) { int j = i + len - 1; dp[i][j] = INT_MAX; for (int k = i; k < j; ++k) { // Compute the cost of multiplying matrices from i to k // and from k+1 to j, and add them to the cost of multiplying // the resulting matrices int cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]; if (cost < dp[i][j]) { dp[i][j] = cost; bracket[i][j] = k; // Store the index at which the sequence is split } } } } // Print the optimal parenthesized sequence order char name = 'A'; std::cout << "Optimal Parenthesized Sequence Order: "; printParenthesis(0, n - 1, bracket, name); std::cout << std::endl; return dp[0][n - 1]; } int main() { // Input the dimensions of the matrices std::vector<int> dims = {10, 100, 5, 50}; // Find the minimum cost required to multiply the matrices int minCost = matrixChainOrder(dims); // Print the minimum cost std::cout << "Minimum Cost: " << minCost << std::endl; return 0; }