DP---矩阵连乘

动态规划法是解决问题的一种方法。它不规定为了得到结果需如何将问题划分为子问题的固定方法，而是按不同输入给出问题的具体实例的子问题划分方法，然后再进行运算、解答问题。
 
矩阵连乘问题的主要思想如下：
1）设置大小为连乘个数的方阵
2）主对角线上方各元素Di,j(ij)表示矩阵Mi连乘到Mj的最小工作量
3）下方元素Di,j(i> j)记录获得该最小工作量矩阵分组的第一组的最后一个矩阵的序列号
 最后通过下方元素可知最终结果的分组方式。
 
算法描述：
1）读入n, 即矩阵的个数;
2）读入n+1个数, 即n个矩阵的行数和列数, 将它们存入数组r中;
3）将d主对角线元素置为零;
4）求出d矩阵的其它元素的数值;
5）给出n个矩阵的结合方式.
 
Code：

[htML] 
#define MAXINT 1000 
int D[10][10],R[11];  
void PRint(int i, int j) 
{  
    int k;  
    if(i==j) printf("m%d",i);  
    else if (i+1==j) printf("M%d,M%d",i,j);  
    else 
    {  
        k =D[j][i];  
        printf(" (");  
        print(i,k);  
        print(k+1, j);  
        printf(")");  
    }  
}  
 
DM(int N) 
{  
    int I,J,K,T;  
    for(I=1; IN-1; i++) 
        for(J=1; JN-1; J++) 
        {  
            D[J][J+1]=MAXINT;  
            for(K=0; KI-1; K++) 
            {  
                T=D[J][J+K]+D[J+K+1][J+1]+R[J-1]*R[J+K]*R[J+1];  
                if(TD[J][J+1]) 
                {  
                    D[J][J+1]=T;  
                    D[J][J+1]=J+K;  
                }  
            }  
        }  
}  
 
main() 
{  
    int flag=1,N,i;  
    char c;  
    printf("e------exIT     i--------continue/n");  
    while(flag==1) 
    {  
        scanf("%c",& c);  
        switch(c) 
        {  
        case 'i':   flag=1;  
            printf("Please Input The Data:/n");  
            printf("The value of matrix: N=");   
            scanf("%d",& N);  
            for(i=0; iN; i++) 
            {  
                printf("R[i]=",i);  
                scanf("%d",& R[i]);  
            }  www.2cto.COM
            for(i=1; iN; i++)  D[i][i]=0;  
            DM(N);  
            print(1,N+1);  
            break;  
        case 'e':  flag=0; break;  
        }  
    }  
}  

动态规划法是解决问题的一种方法。它不规定为了得到结果需如何将问题划分为子问题的固定方法，而是按不同输入给出问题的具体实例的子问题划分方法，然后再进行运算、解答问题。
 
矩阵连乘问题的主要思想如下：
1）设置大小为连乘个数的方阵
2）主对角线上方各元素Di,j(ij)表示矩阵Mi连乘到Mj的最小工作量
3）下方元素Di,j(i> j)记录获得该最小工作量矩阵分组的第一组的最后一个矩阵的序列号
 最后通过下方元素可知最终结果的分组方式。
 
算法描述：
1）读入n, 即矩阵的个数;
2）读入n+1个数, 即n个矩阵的行数和列数, 将它们存入数组r中;
3）将d主对角线元素置为零;
4）求出d矩阵的其它元素的数值;
5）给出n个矩阵的结合方式.
 
Code：

[html] 
#define MAXINT 1000 
int D[10][10],R[11];  
void print(int i, int j) 
{  
    int k;  
    if(i==j) printf("M%d",i);  
    else if (i+1==j) printf("M%d,M%d",i,j);  
    else 
    {  
        k =D[j][i];  
        printf(" (");  
        print(i,k);  
        print(k+1, j);  
        printf(")");  
    }  
}  
 
DM(int N) 
{  
    int I,J,K,T;  
    for(I=1; IN-1; I++) 
        for(J=1; JN-1; J++) 
        {  
            D[J][J+1]=MAXINT;  
            for(K=0; KI-1; K++) 
            {  
                T=D[J][J+K]+D[J+K+1][J+1]+R[J-1]*R[J+K]*R[J+1];  
                if(TD[J][J+1]) 
                {  
                    D[J][J+1]=T;  
                    D[J][J+1]=J+K;  
                }  
            }  
        }  
}  
 
main() 
{  
    int flag=1,N,i;  
    char c;  
    printf("e------exit     i--------continue/n");  
    while(flag==1) 
    {  
        scanf("%c",& c);  
        switch(c) 
        {  
        case 'i':   flag=1;  
            printf("Please Input The Data:/n");  
            printf("The value of matrix: N=");   
            scanf("%d",& N);  
            for(i=0; iN; i++) 
            {  
                printf("R[i]=",i);  
                scanf("%d",& R[i]);  
            }  www.2cto.com
            for(i=1; iN; i++)  D[i][i]=0;  
            DM(N);  
            print(1,N+1);  
            break;  
        case 'e':  flag=0; break;  
        }  
    }  
}  

觉得可用，就经常来吧！ 欢迎评论哦！ html5教程，巧夺天工，精雕玉琢。小宝典献丑了！

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！