A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d2/da2/matrix__chain__multiplication_8cpp_source.html below:

TheAlgorithms/C++: dynamic_programming/matrix_chain_multiplication.cpp Source File

7// dp table to store the solution for already computed sub problems 10// Function to find the most efficient way to multiply the given sequence of 12int

MatrixChainMultiplication(

int

dim[],

int

i,

int

j) {

13 // base case: one matrix 17 // stores minimum number of scalar multiplications (i.e., cost) 18 // needed to compute the matrix M[i+1]...M[j] = M[i..j] 21 // if dp[i][j] is not calculated (calculate it!!) 23 if

(

dp

[i][j] == 0) {

24 // take the minimum over each possible position at which the 25 // sequence of matrices can be split 27 for

(

int

k = i + 1;

k

<= j - 1;

k

++) {

28 // recur for M[i+1]..M[k] to get a i x k matrix 29 int

cost = MatrixChainMultiplication(dim, i, k);

31 // recur for M[k+1]..M[j] to get a k x j matrix 32

cost += MatrixChainMultiplication(dim, k, j);

34 // cost to multiply two (i x k) and (k x j) matrix 35

cost += dim[i] * dim[

k

] * dim[j];

38

min = cost;

// store the minimum cost 43 // return min cost to multiply M[j+1]..M[j] 49 // Matrix i has Dimensions dim[i-1] & dim[i] for i=1..n 50 // input is 10 x 30 matrix, 30 x 5 matrix, 5 x 60 matrix 51 int

dim[] = {10, 30, 5, 60};

52 int

n =

sizeof

(dim) /

sizeof

(dim[0]);

54 // Function Calling: MatrixChainMultiplications(dimensions_array, starting, 57

cout <<

"Minimum cost is "

<< MatrixChainMultiplication(dim, 0, n - 1)

double k(double x)

Another test function.

int main()

Main function.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4