矩阵连乘最优结合 动态规划求解

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <limits.h>
 5 #include <string>
 6 using namespace std;
 7 ///计算M矩阵
 8 int calculate_M(vector<vector<int> >&num,vector<pair<int,int> > &data,vector<vector<int> > &points){
 9     int len = data.size();
10     for(int span = 1;span<len;span++){  ///间隔距离
11         for(int col=0;col<len-span;col++){  ///操作起始列
12 
13             for(int i=col;i<col+span;i++){
14                 int tmp = num[col][i] + num[i+1][col+span] + data[col].first*data[i].second*data[col+span].second;
15                 if(tmp < num[col][col+span]){
16                     points[col][col+span] = i;  ///记录分割点
17                     num[col][col+span] = tmp;   ///记录最少乘法次数
18                 }
19             }
20         }
21     }
22     return 0;
23 }
24 
25 ///根据记录的分割点，生成最后的矩阵相乘表达式
26 string make_result(vector<vector<int> > &points,int t1,int t2){
27     if(t1 == t2)
28         return string(1,'A'+t1);
29     int split = points[t1][t2];
30     return "("+make_result(points,t1,split)+"*"+make_result(points,split+1,t2)+")";
31 }
32 
33 int main()
34 {
35     vector<pair<int,int>> data; ///保存矩阵的行、列
36     data.push_back(make_pair(10,100));  //A
37     data.push_back(make_pair(100,5));   //B
38     data.push_back(make_pair(5,25));    //C
39     data.push_back(make_pair(25,15));   //D
40     data.push_back(make_pair(15,20));   //E
41 
42 
43     int len = data.size();
44     vector<vector<int> > num(len,vector<int>(len)); ///定义二维向量，并预先分配空间，记录乘法次数
45     vector<vector<int> > points(len,vector<int>(len)); ///定义二维向量，并预先分配空间，记录分割点
46     for(int i=0;i<len;i++){
47         for(int j=0;j<len;j++){
48             points[i][j] = -1;
49             if(i == j)
50                 num[i][j] = 0;  ///自己和自己相乘，所以为0
51             else
52                 num[i][j] = INT_MAX;    ///否则，记为最大整数值
53         }
54     }
55 
56     calculate_M(num,data,points);
57     cout<<make_result(points,0,len-1)<<"\t最少乘法次数为:"<<num[0][len-1]<<endl;
58     return 0;
59 }