矩阵连乘问题

给定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:

 1#include <iostream>
 2#include <vector>
 3#include <fstream>
 4using namespace std;
 5int m[100][100],s[100][100];
 6int p[100];
 7int 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                    
26            
27
28int 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   
36   cout<<sovle(n-1)<<endl;
37
38   system("pause"); 
39   fin.close();
40
41   return 0;
42}
43

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


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2025年3月>
日一二三四五六
2324252627281
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿

随笔档案(6)

搜索

最新评论

阅读排行榜

评论排行榜