C Program to Perform Optimal Paranthesization Using Dynamic Programming

«
»
This is a C Program to perform optimal paranthesization using DP. This program determines the order in which the chain of matrices should be multiplied.

Here is source code of the C Program to Perform Optimal Paranthesization Using Dynamic Programming. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* A naive recursive implementation that simply follows the above optimal
  2.  substructure property */
  3. #include<stdio.h>
  4. #include<limits.h>
  5.  
  6. int MatrixChainOrder(int p[], int n) {
  7.     /* For simplicity of the program, one extra row and one extra column are
  8.      allocated in m[][].  0th row and 0th column of m[][] are not used */
  9.     int m[n][n];
  10.     int s[n][n];
  11.     int i, j, k, L, q;
  12.  
  13.     /* m[i,j] = Minimum number of scalar multiplications needed to compute
  14.      the matrix A[i]A[i+1]...A[j] = A[i..j] where dimention of A[i] is
  15.      p[i-1] x p[i] */
  16.  
  17.     // cost is zero when multiplying one matrix.
  18.     for (i = 1; i < n; i++)
  19.         m[i][i] = 0;
  20.  
  21.     // L is chain length.
  22.     for (L = 2; L < n; L++) {
  23.         for (i = 1; i <= n - L + 1; i++) {
  24.             j = i + L - 1;
  25.             m[i][j] = INT_MAX;
  26.             for (k = i; k <= j - 1; k++) {
  27.                 // q = cost/scalar multiplications
  28.                 q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
  29.                 if (q < m[i][j]) {
  30.                     m[i][j] = q;
  31.                     s[i][j] = k;
  32.                 }
  33.             }
  34.         }
  35.     }
  36.  
  37.     return m[1][n - 1];
  38. }
  39. int main() {
  40.     printf(
  41.             "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]");
  42.     printf("Enter the total length:");
  43.     int n;
  44.     scanf("%d", &n);
  45.     int array[n];
  46.     printf("Enter the dimensions: ");
  47.     int var;
  48.     for (var = 0; var < n; ++var) {
  49.         scanf("%d", array[var]);
  50.     }
  51.     printf("Minimum number of multiplications is: %d",
  52.             MatrixChainOrder(array, n));
  53.     return 0;
  54. }

Output:

advertisement
$ gcc OptimalParanthesization.cpp
$ ./a.out
 
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:4
Enter the dimensions: 2 4 3 5
Minimum number of multiplications is: 54

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement

Here’s the list of Best Reference Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn