Minimum matrix multiplication

Given 2 arrays A,B, where x(A.length) < y(B.length), we want to insert (y – x) 0’s to A at various places such that A*B is minimum. For instance, if A = (1, -1) and B = (1,2, 3, 4), then inserting two 0’s in the middle of A such that A = (1, 0, 0, -1) would minimize A*B. 

C++:
01 int minPlus(int A[], int n, int B[], int m)
02 {
03     vector<int*> C(n);
04     for(int i=0;i<n;i++)
05         C[i]=new int[m];
06     for(int i=0;i<n;i++)
07         for(int j=0;j<m;j++)
08             C[i][j]=0;
09     C[0][0]=A[0]*B[0];
10     for(int i=1;i<n;i++)
11         C[i][i]=C[i1][i1]+A[i]*B[i];
12     for(int j=1;j<m;j++){
13         if(A[0]*B[j]<C[0][j1])
14             C[0][j]=A[0]*B[j];
15         else
16             C[0][j]=C[0][j1];
17     }
18     for(int i=1;i<n;i++){
19         for(int j=i+1;j<m;j++){
20             int a=C[i1][j1]+A[i]*B[j];
21             int b=C[i][j1];
22             C[i][j]=a<b?a:b;
23         }
24     }
25     return C[n1][m1];
26 }
Advertisements
This entry was posted in Array and linked list, Dynamic programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s