矩阵连乘问题

给定n个矩阵，给这n个矩阵加若干个括号，使得这n个矩阵所用的乘法次数最少。

动态规划的解法：
m[i][j]=min{ m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]}

其中 i<=k<j
code:

#include <iostream>
2

#include <vector>
3

#include <fstream>
4

using namespace std;
5

int m[100][100],s[100][100];
6

int p[100];
7

int sovle(int n){
8

int i,j,k,r;
9

for(i=1;i<=n;i++)m[i][i]=0;
10

for(r=2;r<=n;r++){
11

for(i=1;i<=n-r+1;i++){
12

j=i+r-1;
13

//cout<<"j= "<<j<<endl;
14

int t=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
15

for(k=i+1;k<j;k++){
16

int mt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
17

if(t>mt){t=mt;}
18

}
19

m[i][j]=t;
20

}
21

}
22

cout<<"**"<<m[1][n+3]<<endl;
23

return m[1][n];
24

}
25

int main(){
29

fstream fin("matrix.txt");
30

int n;
31

fin>>n;
32

for(int i=0;i<n;i++){
33

fin>>p[i];
34

}
35

cout<<sovle(n-1)<<endl;
37

system("pause");
39

fin.close();
40

return 0;
42

}
43

posted on 2010-06-06 20:12 bluedream 阅读(335) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。




网站导航: 博客园博客园最新博文博问管理

矩阵连乘问题

导航

统计

常用链接

留言簿

随笔档案(6)

搜索

最新评论

阅读排行榜

评论排行榜