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

DP 矩阵连乘问题

动态规划：

找出最优解的性质，刻画其结构特征。
递归地定义最优值。
以自底向上的方式计算最优值。
根据计算最优值得到的信息构造最优解。

矩阵链乘法问题可表述如下：给定n个矩阵构成的一个链<A1,A2,A3……An>,其中i=1,2,……n,矩阵Ai维数为P.i-1×P.i,对乘积A1·A2·A3···An以最小化标量乘法次数的方式进行加括号。

注：矩阵链问题主要涉及的时在多个矩阵相乘，如何通过相乘的顺序来减少程序运行。

递推规律：
设计算A[i:j]（矩阵A从i乘到j），1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]（上面例题就是m[1][6]）。
当i=j时，A[i:j]=Ai，因此，m[i][i]=0，i=1,2,…,n 当i<j时，若A[i:j]的最优次序在Ak和Ak+1之间断开，i<=k<j,则：m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj。由于在计算是并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i个可能。因此，k是这j-i个位置使计算量达到最小的那个位置。
综上，有递推关系如下：

测试：A1 {30*35} A2{35*15} A3{15*5} A4{5*10} A5{10*20} A6{20*25}

Input

含有多组测试数据，每组测试数据的第一列，含有1个整数N（N <= 10）代表有多少个数组要相乘。接下来有N对整数，代表一数组的列数及栏数。这N个数组的顺序与要你相乘的数组顺序是一样的。N=0代表输入结束。请参考Sample Input。

Output

每组测试数据输出一列，内容为矩阵相乘的顺序（以刮号来表示）使得所用的乘法次数最小。如果有不只一组答案，输出任一组均可。请参考Sample Output。

Sample Input

#include <iostream>
#include<vector>
#include<cstring>
#include<stdio.h>
using namespace std;
int fz[100][100];
int point[100][100]; // 记录最小间断位置 只用1-n 空0号
int maj[100];
char temp;

void trace(int i,int j)
{
    if(i==j)
    {
            cout<<'A'<<i;
    }
     else
    {
        int k;
        cout<<'(';
        k=point[i][j];
        trace(i,k);
        cout<<" x ";
        trace(k+1,j);
        cout<<')';
    }
}

void maj1(int n)
 {
 int i,r,j,k;
    for(r=2;r<=n;r++) //r 间距距离
        for(i=1;i<=n-r+1;i++)
    {
        j=r+i-1;
        fz[i][j]=fz[i+1][j]+maj[i-1]*maj[i]*maj[j]; // 先把第一个，与后面分开
        point[i][j]=i;
        for(k=i+1;k<j;k++) //间断位置
        {
            int minsum=fz[i][k]+fz[k+1][j]+maj[i-1]*maj[k]*maj[j];
            if(minsum<fz[i][j])
            {
                fz[i][j]=minsum;
                point[i][j]=k;  //将间断位置存给point
            }
        }
    }
            trace(1,n);
    }
int main()
{
    int n;int i,j=1;
    int q=1;
    scanf("%d",&n);
    while(n!=0)
    {
            int a[2*n];
            int j=1;
            memset(maj,0,sizeof(maj));
            memset(point,0,sizeof(point));
            memset(fz,0,sizeof(fz));
            memset(a,0,sizeof(a));
            for(i=0;i<2*n;i++)
            {
                scanf("%d",&a[i]);
                fz[i][i]=0;
                point[i][i]=0;
             }
             maj[0]=a[0];
            for(i=1;i<2*n;)
                {
                    maj[j++]=a[i];
                    i=i+2;
                }

                printf("Case %d: ",q);
                q++;
                maj1(n);
                temp='0';
                cout<<'\n';
                scanf("%d",&n);
    }
}

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

Input

Output

推荐阅读