精华内容
下载资源
问答
  • 最优矩阵连乘

    2013-11-22 19:53:48
    Problem 18: 最优矩阵连乘 Time Limit:1 Ms| Memory Limit:128 MB Difficulty:3 Description 一个n*m矩阵由n行m列共n*m个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个N*M的矩阵乘以一...

    Problem 18: 最优矩阵连乘


    Time Limit:1 Ms| Memory Limit:128 MB
    Difficulty:3

    Description

    一个n*m矩阵由n行m列共n*m个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵,运算量为nmp。
    矩阵乘法满足结合律,A*B*C可以表示成(A*B)*C或者是A*(B*C),两者的运算量却不同。例如当A=2*3 B=3*4 C=4*5时,(A*B)*C=64而A*(B*C)=90。显然第一种顺序节省运算量。
    现在给出N个矩阵,并输入N+1个数,第i个矩阵是a[i-1]*a[i]

    Input

    第一行n(n<=100)
    第二行n+1个数

    Output

    最优的运算量

    Sample Input

    3
    2 3 4 5

    Sample Output

    64

    Hint

    动态规划

    表达式上的动态规划,d(i,j)表示从矩阵i到矩阵j的最小运算量则,d(i,j) = max(d(i, k) + d(k + 1, j) + pi - 1 *pk * pj

    \#include <stdio.h>
    int p[102];
    int dp[102][102];
    int main(void){
        int n, j, q;
        scanf("%d", &n);
        for(int i = 0; i <= n; ++i)
        {
            scanf("%d", &p[i]);
        }
        for(int i = 1; i <= n; ++i)
        {
            dp[i][i] = 0;
        }
        for(int l = 2; l <= n; ++l)
        {
            for(int i = 1; i <= n - l + 1; ++i)
            {
                j = i + l - 1;
                dp[i][j] = -1;
                for(int k = i; k <= j - 1; ++k)
                {
                    q = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                    if(dp[i][j] == -1)
                        dp[i][j] = q;
                    else if(q < dp[i][j])
                        dp[i][j] = q;
                }
            }
        }
        printf("%d\n",dp[1][n]); 
        return 0;
    }
    



    展开全文
  • 最优矩阵连乘的递推写法,备忘录写法,及其用一个二维数组保存最优结果,然后递归打印。 #include <bits/stdc++.h> using namespace std; const int maxn = 100; const int inf = 0x3f3f3f3f; int s[maxn]...

    最优矩阵连乘的递推写法,备忘录写法,及其用一个二维数组保存最优结果,然后递归打印。

    #include <bits/stdc++.h>
    
    using namespace std;
    
    const int maxn = 100;
    const int inf = 0x3f3f3f3f;
    
    
    int s[maxn][maxn];
    struct Mart {
        int h, w;
    }mart[maxn];
    
    int get_ans(int n, int d[][maxn], int *p) {
        for(int i = 0; i <= n; i++) d[i][i] = 0;
        for(int len = 2; len <= n; len++) {
            for(int i = 1; i <= n; i++) {
                int j = i + len - 1;
                if(j > n) break;
                d[i][j] = inf;
    
                for(int k = i; k < j; k++) {
    //                d[i][j] = min(d[i][j], d[i][k] + d[k+1][j] + p[i-1]*p[k]*p[j]);
                    if(d[i][j] > d[i][k] + d[k+1][j] + p[i-1]*p[k]*p[j]) {
                        d[i][j] = d[i][k] + d[k+1][j] + p[i-1]*p[k]*p[j];
                        s[i][j] = k;
                    }
                }
            }
        }
        return d[1][n];
    }
    int get_Ans(int l, int r, int d[][maxn], int *p) {
        if(~d[l][r]) return d[l][r];
        if(l == r) return d[l][r] = 0;
        d[l][r] = inf;
        for(int k = l; k < r; k++) {
    //        d[l][r] = min(d[l][r], get_Ans(l, k, d, p) + get_Ans(k+1, r, d, p) + p[l-1] * p[k] * p[r]);
            if(d[l][r] > get_Ans(l, k, d, p) + get_Ans(k+1, r, d, p) + p[l-1] * p[k] * p[r]) {
                d[l][r] = get_Ans(l, k, d, p) + get_Ans(k+1, r, d, p) + p[l-1] * p[k] * p[r];
                s[l][r] = k;
            }
        }
        return d[l][r];
    }
    
    void print_ans(int l, int r) {
        if(l == r) {
            printf("A%d", l);
            return ;
        }
        int k = s[l][r];
        printf("(");
        print_ans(l, k);
        print_ans(k+1, r);
        printf(")");
    }
    
    int main()
    {
    //    freopen("i.txt", "r", stdin);
        int d[maxn][maxn],p[maxn];
        int n;
        scanf("%d", &n);  // 输入矩阵的个数
        for(int i = 1; i <= n; i++) {
            scanf("%d%d", &mart[i].h, &mart[i].w);  // 矩阵的高and宽
        }
        for(int i = 0; i <= n; i++) {
            if(i == 0) {
                p[i] = mart[i+1].h;
            }
            else p[i] = mart[i].w;
        }
        printf("动态规划方法 ans = %d\n", get_ans(n, d, p));
        print_ans(1, n);
        putchar('\n');
        memset(d, -1, sizeof(d));
        printf("-------------------------------------------\n");
        printf("备忘录方法   ans = %d\n", get_Ans(1, n, d, p));
        print_ans(1, n);
        putchar('\n');
        return 0;
    }
    
    
    展开全文
  • 思路:这道题与最优矩阵连乘的思想一样,那就是分析最优子结构,再根据子结构来定义状态,首先我们假定第一次分割的最优方案是在k处分割,得到0~k与k~L两段木棍,那么如何最优分割0~k与0~L就是它的子问题,我们根据...

    题意:有一根长度为L的木棍,和n个切割点的位置(按照从小到大排序),你的任务是在这些切割点的位置把棍子切成n+1份,使得总切割费用最小。每次切割的费用等于被切的木棍长度

    思路:这道题与最优矩阵连乘的思想一样,那就是分析最优子结构,再根据子结构来定义状态,首先我们假定第一次分割的最优方案是在k处分割,得到0~k与k~L两段木棍,那么如何最优分割0~k与0~L就是它的子问题,我们根据子问题定义状态d(i,j)是分割从割点i到割点j的最优方案,状态转移方程 d(i,j)=min{d(i,k)+d(k,j)+(cut[j]-cut[i])}(其中i<k<j),接下来是确定边界,d(i,i)=0 和 d(i,i+1)=0,并注意赋初值INF

    代码:

    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #define INF 0x3f3f3f3f
    
    using namespace std;
    int d[55][55];
    int cut[55];
    bool visit[55][55];
    int L,n;
    
    int dp(int i,int j)
    {
        if((j-i)<=1) return 0;
        if(visit[i][j]==true) return d[i][j];
        visit[i][j]=true;
        for(int k=i+1;k<j;k++)
            d[i][j]=min(d[i][j],dp(i,k)+dp(k,j)+(cut[j]-cut[i]));
        return d[i][j];
    }
    
    int main(int argc, char const *argv[])
    {
        while(cin>>L&&L)
        {
            cin>>n;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&cut[i]);
            }
            cut[0]=0;
            cut[n+1]=L;
            memset(visit,false,sizeof(visit));
            memset(d,INF,sizeof(d));
            int ans=dp(0,n+1);
            cout<<"The minimum cutting is "<<ans<<"."<<endl;
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/simplekinght/p/6953258.html

    展开全文
  • 动态规划之最优矩阵连乘

    千次阅读 2012-08-14 10:30:34
    最优矩阵连乘 问题描述: 一个n*m矩阵由n行m列共n*m个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵,运算量为nmp。 矩阵乘法满足结合律,A*B*...

    最优矩阵连乘

    问题描述:

    一个n*m矩阵由n行m列共n*m个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵,运算量为nmp。
    矩阵乘法满足结合律,A*B*C可以表示成(A*B)*C或者是A*(B*C),两者的运算量却不同。例如当A=2*3 B=3*4 C=4*5时,(A*B)*C=64而A*(B*C)=90。显然第一种顺序节省运算量。
    现在给出N个矩阵,并输入N+1个数,第i个矩阵是a[i-1]*a[i]。

    输入:

    第一行n(n<=100)
    第二行n+1个数

    输出:

    最优的运算量

    样例输入:

    3

    2 3 4 5

    样例输出:

    64

    代码:

    #include <iostream>
    using namespace std;
    #define N 105
    int c[N][N],s[N][N],p[N];
    int chain(int i,int j)
    {
    	if(c[i][j]>0)return c[i][j];
    	if(i==j)return 0;
    	int u=chain(i,i)+chain(i+1,j)+p[i-1]*p[i]*p[j];
    	s[i][j]=i;
    	for(int k=i+1;k<j;k++)
    	{
    		int t=chain(i,k)+chain(k+1,j)+p[i-1]*p[k]*p[j];
    		if(t<u)
    		{
    			u=t;
    			s[i][j]=k;
    		}
    		
    		
    	}
    	c[i][j]=u;
    	return u;
    }
    int main(int argc, char *argv[])
    {
    	int n,i,j;
    	cin>>n;
    	for(i=0;i<=n;i++)
    	cin>>p[i];
    	cout<<chain(1,n)<<endl;
    	return 0;
    }


     

    展开全文
  • 最优矩阵连乘问题

    2015-03-31 19:12:34
    1.引言 多矩阵连乘 对于一般的矩阵乘法来说,如矩阵A(m,n)与矩阵B(n,p)相乘需要进行的加法次数为m*n*p次乘法。 由于矩阵乘法满足结合律,因此矩阵相乘的结合性,会影响整个计算表达式的乘法执行次数。 如...
  • 最优矩阵连乘积 Accepted: 10 Total Submit: 18 Time Limit: 1000ms Memony Limit: 32768KB Description 在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×...
  • tyvj1198 最优矩阵连乘

    2016-08-09 21:20:00
    一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵,运算量为nmp。矩阵乘法满足结合律,A*B*C可以表示成(A*B)*C或者是A*(B*C),两者的运算量却不同。例如当A=2*3B=3*4C=4*5时,(A*B)*C=64而A*(B*C)=90。显然第一种.....
  • \noindent {\color{blue}动态规划最优矩阵连乘问题:} \hangafter=1\setlength{\hangindent}{0em}给定n个矩阵{A1,A2,…,An},其中Ai 与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此...
  • 如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。例如,给定三个连乘矩阵{A1,A2,A3}的维数分别是10100,1005和550,采用(A1A2)A3,乘法次数为101005+10550=7500次,而采用A1...
  • 算法提高 矩阵乘法 时间限制:**3.0s 内存限制:**256.0MB 问题描述  有n个矩阵,大小分别为a0*a1, a1*a2, a2*a3, …, a[n-1]*a[n],现要将它们依次相乘,只能使用结合率,求最少需要多少次运算。  两个大小...
  • 思路:最优矩阵问题,典型的动态规划题目。 该问题的子问题为“把Ai,Ai+1,……,Aj起来需要多少次乘法”,如果用dp(i,j)表示这个问题的子问题的值, 则状态转移方程:dp(i,j) = min{dp(i,k) + dp(k+1,j) +...
  • 题目大意:求那个矩阵连乘的最小运算量 思路是采用动态规划: 设a[n][m]为第n个矩阵到第m个矩阵连乘的最小乘法数(n, m >= 1),b[i], b[i -1]为第i个矩阵的行数和列数(i >= 1),那么: 1.a[n]
  • 题目大意:给出N个矩阵,要求所有矩阵相乘的值达到最小值
  • 最优矩阵

    2016-08-04 16:40:55
    最优矩阵连乘问题描述:一个n*m矩阵由n行m列共n*m个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵,运算量为nmp。 矩阵乘法满足结合律,A*B*C...
  • 和最优矩阵链乘模型一样,最后取出的数决定了序,如果没学过最优矩阵连乘找重复子问题还是比较难找的 DP //180K 0MS #include #include #include #include using namespace std; int dp[110][110];
  • NBUT 1003 最优矩阵

    2019-07-02 14:47:40
    如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 思路:如果最后一次乘法是第k个,则从A1,A2,....Ak和Ak+1,Ak+2......An两个子序列都是最优乘法了,所以我们只需保证两个子结构...
  • 如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。例如:  A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ; 最后的结果为:((A1(A2A3))((A4A5)A6).....
  • 最优矩阵 动态规划

    千次阅读 2016-04-25 20:55:40
    矩阵连乘问题----动态规划(转载): 给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。 解答:我们按照动态...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 253
精华内容 101
关键字:

最优矩阵连乘