矩阵连乘问题

矩阵连乘问题（动态规划）

　　给定 n 个矩阵 {A₁,A₂,...,A_n}, 其中 A_i 与 A_i+1 是可乘的（i=1,2,...,n-1）。考察这 n 个矩阵的连乘积 A₁A₂···A_n ，记录最优值和最优断点位置。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 

 

源代码：

 

//矩阵连乘问题
/*测试数据
6
30 35 15 5 10 20 25
*/

 

#include<iostream>
#include <limits.h>  //极限值头文件，INT_MAX无穷大，INT_MIN无穷小

 

using namespace std;

 

void MatrixChain(int *p,int n,int **m,int **s)
{
    int i,l,j,k,t;
    for(int i=1;i<=n;i++)
 {
  m[i][i]=0;             //单一矩阵的情况  一个矩阵数乘次数为0
  s[i][i]=0;
 }
    for(l=2;l<=n;l++)    //相乘矩阵的区间（l：相乘矩阵个数）   l为段长
    {
        for(i=1;i<=n-l+1;i++)
        {
            j=i+l-1;
            m[i][j]=INT_MAX;  //INT_MAX（无穷大）
            for(k=i;k<=j-1;k++)     //改变断点，试探出最小的情况
            {
                t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(t<m[i][j])
                {
                    m[i][j] = t;
                    s[i][j] = k;     //记录断点位置
                }
            }
        }
    }
}

 

int main ()
{
    int num;
 int *dimension;
 int **mm;
 int **ss;
 cin>>num;    //相乘矩阵个数

 

 dimension=new int[num+1];     //矩阵维数

 

 //创建动态二维数组
    mm=new int*[num+1];
 ss=new int*[num+1];
 for(int i=0;i<num+1;i++)
 {
  mm[i]=new int[num+1];
  ss[i]=new int[num+1];
 }

 

 //赋初值
 for(int j=0;j<num+1;j++)
    {
        for(int k=0;k<num+1;k++)
        {
            mm[j][k]=-1;
            ss[j][k]=-1;
        }
    }

 

    //输入数据
 for(int r=0;r<=num;r++)
  cin>>dimension[r];

 

 MatrixChain(dimension,num,mm,ss);

 

 for(int j=1;j<=num;j++)  //记录最优值
    {
        for(int k=1;k<=num;k++)
            cout<<mm[j][k]<<"\t";
        cout<<endl;
    }
    cout<<endl;

 

    for(int j=1;j<=num;j++)  //记录最优断点位置
    {
        for(int k=1;k<=num;k++)
            cout<<ss[j][k]<<"\t";
        cout<<endl;
    }

 

    //释放空间
    delete[] dimension;

 

    for(int i=0;i<num+1;i++)
 {
  delete[] mm[i];
  delete[] ss[i];
 }
    delete[] mm;
    delete[] ss;
    return 0;
}     运行界面：  

 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄