算法设计与分析课

实验三

第一题

矩阵连乘问题：

分析：该问题求矩阵连乘积最少乘次数，对于两个矩阵A(i行j列)和B(j行n列)，他们相乘的乘次数为ijn，对于两个矩阵只有它们的列和行相等才能相乘。

用数组A接受矩阵的行列，对于一个矩阵An，其行为A[n-1]，列为A[n]，题目中给了Ai与Ai+1是可以相乘的。用数组M表示矩阵链相乘的最优解，例如M[i][j]表示从矩阵i到矩阵j的矩阵链相乘的最小计算次数。

利用动态规划求解，对于每一个矩阵链，其中的矩阵不断相乘，最后剩下两个矩阵相乘得到最后的矩阵，记它们在k处断开。但是k的值不确定，需要计算，所以动态规划就得到了解决公式。

如果i=j，则M[i][j]=0。

如果i<j，则M[i][j]等于min{M[i][k]+M[k+1][j]+Ai-1 * Ak * Aj}。

解决代码：

#include<iostream>
#include<cstring>
#define maxn 1000+5
#define inf 0x3f3f3f3f
using namespace std;

//利用动态规划求解
//用数组A接受矩阵的行列，对于一个矩阵An，其行为A[n-1]，列为A[n]，题目中给了Ai与Ai+1是可以相乘的
//用数组M表示矩阵链相乘的最优解，例如M[i][j]表示从矩阵i到矩阵j的矩阵链相乘的最小计算次数
//分析矩阵链的相乘，乘到最后只剩下两个矩阵相乘然后得到最终的矩阵，那么可以假设该矩阵链最后的相乘是从k处断开的
//但是k的值不确定，需要计算，所以动态规划就得到了解决公式
//如果i=j，则M[i][j]=0，如果i<j，则M[i][j]等于min{M[i][k]+M[k+1][j]+pi-1*pk*pj}
//其中p为矩阵的行列

int M[maxn][maxn];//记录矩阵链相乘的最优解
int S[maxn][maxn];//记录矩阵链相乘的断开点
int A[maxn];//记录矩阵
int n;//矩阵个数

void MatrixMultiply(int A[], int n, int M[][maxn], int S[maxn][maxn]);
void PrintWay(int S[][maxn], int l, int r);

int main()
{
    int n;
    cin>>n;
    for(int i=0; i<=n; i++) cin>>A[i];
    //memset(S, -1, sizeof(S));
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            S[i][j]=-1;
    MatrixMultiply(A, n, M, S);
    cout<<M[1][n]<<endl;
    //cout<<S[1][1]<<endl;
    PrintWay(S, 1, n);
    return 0;
}

void MatrixMultiply(int A[], int n, int M[][maxn], int S[maxn][maxn])
{
    //memset(M, inf, sizeof(M));
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            M[i][j]=inf;

    for(int i=1; i<=n; i++) M[i][i]=0;

    for(int len=2; len<=n; ++len)//矩阵链的长度
    {
        for(int i=1; i<=n-len+1; ++i)
        {
            int j=i+len-1;//最后一个矩阵的列

            /*不给数组M设置初值的写法，初始认为k为i
            M[i][j]=M[i][i]+M[i+1][j]+A[i-1]*A[i]*A[j];//可以不写M[i][j]，因为该元素值为0
            S[i][j]=i;
            for(int k=i+1; k<j; ++k)
            {
                if(M[i][k]+M[k+1][j]+A[i-1]*A[k]*A[j]<M[i][j])
                {
                    M[i][j]=M[i][k]+M[k+1][j]+A[i-1]*A[k]*A[j];
                    S[i][j]=k;
                }
            }
            */
            for(int k=i; k<j; ++k)
            {
                if(M[i][k]+M[k+1][j]+A[i-1]*A[k]*A[j]<M[i][j])
                {
                    M[i][j]=M[i][k]+M[k+1][j]+A[i-1]*A[k]*A[j];
                    S[i][j]=k;
                }
            }
        }
    }
}

void PrintWay(int S[][maxn], int l, int r)
{
    if(S[l][r]!=-1)
    {
        PrintWay(S, l, S[l][r]);
        PrintWay(S, S[l][r]+1, r);
        cout<<"Multiply A"<<l<<","<<S[l][r]<<" and A"<<S[l][r]+1<<","<<r<<endl;
    }
    else
    {
        return ;
    }
}