Friday, 2 May 2014

Matrix chain multiplication

An array P is given of n+1 positive integers, p[0],..,p[n]. This array should be viewed as a representation of the orders of the n matrices. In particular, A1 is a matrix of order p[0] X p[1], and A2 is a matrix of order p[1] X p[2]. In general, for each i in the range 1 <= i < = n, the order of Ai is p[i-1] X p[i].
Write a program to find the minimum number of multiplication operations to compute the product A1 X A2 X … X An. 

Input: First line contains n, the size of the array. Second line contains elements of p separated by spaces. 
Output: Minimum number of multiplications to multiply the chain.





#include<stdio.h>
#include<limits.h>
#include<stdlib.h> 
int MatrixChainOrder(int p[],int n);
int main()
{
 int n,i;
 scanf("%d",&n);
 int *p = (int *)malloc(sizeof(int)*n);
 for(i=0;i<n;i++)
  scanf("%d",&p[i]);
  printf("%d",MatrixChainOrder(p, n));
    return 0;
}
nt MatrixChainOrder(int p[], int n)
{
 int i,j,k,l,q,m[n][n];
 for(i=1;i<=n;i++)
 {
  m[i][i]=0;
 }
 for(l=2;l<=n;l++)
 {
  for(i=1;i<=n-l+1;i++)
  {
   j=i+l-1;
   m[i][j] = 99999;
   for(k=i;k<=j-1;k++)
   {
    q=m[i][k] + m[k+1][j] + (p[i-1]*p[k]*p[j]);
    if(q<m[i][j])
    {
     m[i][j]=q;
    }
   }
  }
 }
 return m[1][n-1];
}

No comments: