fork download
  1. //
  2. // main.cpp
  3. // Matrix Chain Multiplication
  4. //
  5. // Created by Himanshu on 17/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <climits>
  10. using namespace std;
  11. const int N = 5;
  12.  
  13. void MatrixChainMultiplication (int p[]) {
  14.  
  15. int M[N][N];
  16. for (int i=0; i<N; i++) {
  17. for (int j=0; j<N; j++) {
  18. if (i == j) {
  19. M[i][j] = 0;
  20. } else {
  21. M[i][j] = INT_MAX;
  22. }
  23. }
  24. }
  25.  
  26. // c is the length of chained matrices
  27. for (int c=2; c<N; c++) {
  28. for (int i=1; i<(N-c+1); i++) {
  29. int j = i+c-1;
  30. for (int k=i; k<j; k++) {
  31. M[i][j] = min(M[i][j], (M[i][k] + M[k+1][j] + p[i-1]*p[k]*p[j]));
  32. }
  33. }
  34. }
  35.  
  36. cout<<M[1][N-1]<<endl;
  37.  
  38. }
  39.  
  40. int main() {
  41. //For matrices M1(5x4), M2(4x6), M3(6x2), M4(2x7)
  42. int A[] = {5, 4, 6, 2, 7};
  43. MatrixChainMultiplication(A);
  44. }
  45.  
  46.  
Success #stdin #stdout 0s 5528KB
stdin
Standard input is empty
stdout
158