矩阵链相乘（c++实现）

本文主要是介绍矩阵链相乘（c++实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

《算法导论》书中算法的实现，

#include<iostream>
#include<vector>
#include<limits>
using std::vector;
using std::cout;
using std::cin;
void Print_Optimal_Parens(vector<vector<int> > s,int i,int j)
{if(i==j)cout<<"A"<<i;else{cout<<"(";Print_Optimal_Parens(s,i,s[i-1][j-1]);Print_Optimal_Parens(s,s[i-1][j-1]+1,j);cout<<")";}
}
void Matrix_Chain_order(vector<int> p,vector<vector<int> > &m,vector<vector<int> >&s)
{int n=p.size()-1;for(int i=1;i!=n+1;++i)m[i-1][i-1]=0;for(int l=2;l!=n+1;++l){for(int i=1;i!=n-l+2;++i){int j=i+l-1;m[i-1][j-1]=INT_MAX;for(int k=i;k!=j;++k){int q=m[i-1][k-1]+m[k][j-1]+p[i-1]*p[k]*p[j];if(q<m[i-1][j-1]){m[i-1][j-1]=q;s[i-1][j-1]=k;}}}}
}
int main()
{int aa[]={30,35,15,5,10,20,25};vector<int>p(aa,aa+sizeof(aa)/sizeof(aa[0]));int n=p.size()-1;vector<vector<int> >m(n,vector<int>(n));vector<vector<int> >s(n,vector<int>(n));Matrix_Chain_order(p,m,s);Print_Optimal_Parens(s,1,n);cin.get();
}

这篇关于矩阵链相乘（c++实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---