C++动态规划算法实现矩阵链乘法

2024-10-05 06:12:25

问题描述：

给定n个矩阵的链<A1,A2,…,An>，矩阵Ai的规模为p(i-1)×p(i) (1<=i<=n)，求完全括号化方案，使得计算乘积A1A2…An所需标量乘法次数最少。

动态规划的第一步是寻找最优子结构，然后就可以利用这种子结构从子问题的最优解构造出原问题的最优解。在矩阵链乘法问题中，我们假设A(i)A(i+1)…A(j)的最优括号方案的分割点在A(k)和A(k+1)之间。那么，继续对“前缀”子链A(i)A(i+1)…A(k)进行括号化时，我们应该直接采用独立求解它时所得的最优方案。

递归实现：

　①对于i=j的情况下，显然有m=0，不需要做任何标量乘法运算。所以，对于所有的i=1、2…n，m[i，i] = 0.

　②当i < j的情况，就按照最优括号化方案的结构特征进行计算m[i,j]。假设最优括号化方案的分割点在矩阵Ak和Ak+1之间，那么m的值就是Ai…k和Ak+1…j的代价加上两者量程的代价的最小值。即。该公式的假设是最优分割点是已知的，但是实际上不知道。然而，k只有j-i中情况取值。由于最优分割点k必定在i~j内取得，只需要检查所有可能的情况，找到最优解即可。可以得出一个递归公式

代码实现【C++】

#include <iostream>
using namespace std;
#define N 6
#define MAXVALUE 1000000
void matrix_chain_order(int *p,int len,int m[N+1][N+1],int s[N+1][N+1]);
void print_optimal_parents(int s[N+1][N+1],int i,int j);
int main()
{
    int p[N+1] = {30,35,15,5,10,20,25};
    int m[N+1][N+1]={0};
    int s[N+1][N+1]={0};
    int i,j;
    matrix_chain_order(p,N+1,m,s);
    cout<<"m value is: "<<endl;
    for(i=1;i<=N;++i)
    {
        for(j=1;j<=N;++j)
            cout<<m[i][j]<<" ";
        cout<<endl;
    }
    cout<<"s value is: "<<endl;
    for(i=1;i<=N;++i)
    {
        for(j=1;j<=N;++j)
            cout<<s[i][j]<<" ";
        cout<<endl;
    }
    cout<<"The result is:"<<endl;
    print_optimal_parents(s,1,N);
    return 0;
}
void matrix_chain_order(int *p,int len,int m[N+1][N+1],int s[N+1][N+1])
{
    int i,j,k,t;
    for(i=0;i<=N;++i)
        m[i][i] = 0;
    for(t=2;t<=N;t++)  //当前链乘矩阵的长度
    {
        for(i=1;i<=N-t+1;i++)  //从第一矩阵开始算起，计算长度为t的最少代价
        {
            j=i+t-1;//长度为t时候的最后一个元素
            m[i][j] = MAXVALUE;  //初始化为最大代价
            for(k=i;k<=j-1;k++)   //寻找最优的k值，使得分成两部分k在i与j-1之间
            {
                int temp = m[i][k]+m[k+1][j] + p[i-1]*p[k]*p[j];
                if(temp < m[i][j])
                {
                    m[i][j] = temp;   //记录下当前的最小代价
                    s[i][j] = k;      //记录当前的括号位置，即矩阵的编号
                }
            }
        }
    }
}
//s中存放着括号当前的位置
void print_optimal_parents(int s[N+1][N+1],int i,int j)
{
    if( i == j)
        cout<<"A"<<i;
    else
    {
        cout<<"(";
        print_optimal_parents(s,i,s[i][j]);
        print_optimal_parents(s,s[i][j]+1,j);
        cout<<")";
    }
}

结果

到此这篇关于C++动态规划算法实现矩阵链乘法的文章就介绍到这了,更多相关C++矩阵链乘法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++实现LeetCode(152.求最大子数组乘积)

[LeetCode] 152. Maximum Product Subarray 求最大子数组乘积 Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. Example 1: Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has
C++实现LeetCode(53.最大子数组)

[LeetCode] 53. Maximum Subarray 最大子数组 Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1]
c++动态规划经典算法

目录基本思想重要分析问题方法动态规划算法实例 1.台阶问题 2.从矩阵左上角走到右下角最短路径问题 3.最大子数组问题 4.最长公共子序列基本思想动态规划算法通常用于求解具有某种最优性质的问题.在这类问题中,可能会有许多可行解.每一个解都对应于一个值,我们希望找到具有最优值的解.动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解.与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的.若用分
C++动态规划之最长公子序列实例

本文实例讲述了C++动态规划之最长公子序列解决方法.分享给大家供大家参考.具体分析如下: 问题描述: 求出两个字符串中的最长公子序列的长度. 输入: csblog belong 输出: max length = 4 实现代码: #include <stdio.h> #include <string.h> int arr[200][200]; /* 表示str1的前i位和str2的前j位的最长公子序列的长度 */ int main() { char str1[100],str2[10
C++动态规划计算最大子数组

目录例题 1.求最大的子数组的和 2.求和最大的相应子数组例题题目:输入一个整形数组,数组里有正数也有负数.数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和.求所有子数组的和的最大值.要求时间复杂度为O(n). 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18. 1.求最大的子数组的和代码[C++] #include <iostream> using namespace std
C++动态规划之背包问题解决方法

本文实例讲述了C++动态规划之背包问题解决方法.分享给大家供大家参考.具体分析如下: 问题描述: 背包的最大容量为W,有N件物品,每件物品重量为w,价值为p,怎样选择物品能使得背包里的物品价值最大? 输入: 10 3 (W,N) 4 5 (w,p) 6 7 (w,p) 8 9 (w,p) 实现代码: #include <stdio.h> #define THING 20 #define WEIGHT 100 int arr[THING][WEIGHT]; /* 背包容量为wei
C++ 动态规划算法使用分析

目录 Fibonacci 字符串分割(Word Break) 三角矩阵(Triangle) 路径总数(Unique Paths) 最小路径和(Minimum Path Sum) Fibonacci 题目描述: 大家都知道斐波那契数列,现在要求输入一个正整数 n ,请你输出斐波那契数列的第 n 项. 解题思路: 1.递归 2.动态规划状态:F(n) 状态递推:F(n)=F(n-1)+F(n-2) 初始值:F(1)=F(2)=1 返回结果:F(N) 代码实现: 法一:递归(效率低): class
C++动态规划实现查找最长公共子序列

目录最长公共子序列代码实现结果最长公共子序列最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题.一个数列 ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则称为已知序列的最长公共子序列. 动态规划: 采用二维数组flag来记录下标i和j的走向.数字"1"表示,斜向下:数字"2"表示,水平向右:数字"3"表示,竖直向下问题描述: 设有字符串a[0…n],b[0…m]
C++编辑距离（动态规划）

题目描述: 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 . 我们可以对一个单词进行如下三种操作: 插入一个字符删除一个字符替换一个字符编辑距离:是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数.问题:word1到word2的编辑距离子问题:word1前i个字符到word2前j个字符的编辑距离假如有两个字符串"hat"和"wtct"每个格子表示word1前i个字符到word2前j个字符的编
C++动态规划算法实现矩阵链乘法

问题描述: 给定n个矩阵的链<A1,A2,…,An>,矩阵Ai的规模为p(i-1)×p(i) (1<=i<=n),求完全括号化方案,使得计算乘积A1A2…An所需标量乘法次数最少. 动态规划的第一步是寻找最优子结构,然后就可以利用这种子结构从子问题的最优解构造出原问题的最优解.在矩阵链乘法问题中,我们假设A(i)A(i+1)…A(j)的最优括号方案的分割点在A(k)和A(k+1)之间.那么,继续对“前缀”子链A(i)A(i+1)…A(k)进行括号化时,我们应该直接采用独立求解它时所
Java矩阵连乘问题(动态规划)算法实例分析

本文实例讲述了Java矩阵连乘问题(动态规划)算法.分享给大家供大家参考,具体如下: 问题描述:给定n个矩阵:A1,A2,...,An,其中Ai与Ai+1是可乘的,i=1,2...,n-1.确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少.输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数. 问题解析:由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序.这种计算次序可以用加括号的方式来确定.若一个矩阵连乘积的计算次序完全确
python实现对求解最长回文子串的动态规划算法

基于Python实现对求解最长回文子串的动态规划算法,具体内容如下 1.题目给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为1000. 示例 1: 输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案. 示例 2: 输入: "cbbd" 输出: "bb" 2.求解对于暴力求解在这里就不再骜述了,着重介绍如何利用动态规划算法进行求解. 关于动态规划的含
Python基于动态规划算法计算单词距离

本文实例讲述了Python基于动态规划算法计算单词距离.分享给大家供大家参考.具体如下: #!/usr/bin/env python #coding=utf-8 def word_distance(m,n): """compute the least steps number to convert m to n by insert , delete , replace . 动态规划算法,计算单词距离 >>> print word_distance("
Python基于动态规划算法解决01背包问题实例

本文实例讲述了Python基于动态规划算法解决01背包问题.分享给大家供大家参考,具体如下: 在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决.n=5是物品的数量,c=10是书包能承受的重量,w=[2,2,6,5,4]是每个物品的重量,v=[6,3,5,4,6]是每个物品的价值,先把递归的定义写出来: 然后自底向上实现,代码如下: def bag(n,c,w,v): re
对numpy 数组和矩阵的乘法的进一步理解

1.当为array的时候,默认d*f就是对应元素的乘积,multiply也是对应元素的乘积,dot(d,f)会转化为矩阵的乘积, dot点乘意味着相加,而multiply只是对应元素相乘,不相加 2.当为mat的时候,默认d*f就是矩阵的乘积,multiply转化为对应元素的乘积,dot(d,f)为矩阵的乘积 3. 混合时候的情况,一般不要混合混合的时候默认按照矩阵乘法的, multiply转化为对应元素的乘积,dot(d,f)为矩阵的乘积总结:数组乘法默认的是点乘,矩阵默认的是矩阵乘法,混
Python实现基于POS算法的区块链

区块链中的共识算法在比特币公链架构解析中,就曾提到过为了实现去中介化的设计,比特币设计了一套共识协议,并通过此协议来保证系统的稳定性和防攻击性. 并且我们知道,截止目前使用最广泛,也是最被大家接受的共识算法,是我们先前介绍过的POW(proof of work)工作量证明算法.目前市值排名前二的比特币和以太坊也是采用的此算法. 虽然POW共识算法取得了巨大的成功,但对它的质疑也从来未曾停止过. 其中最主要的一个原因就是电力消耗.据不完全统计,基于POW的挖矿机制所消耗的电量是非常巨大的,甚至比
java动态规划算法——硬币找零问题实例分析

本文实例讲述了java动态规划算法--硬币找零问题.分享给大家供大家参考,具体如下: 问题描述现在有3种硬币分别为:1元,5元,10元,现在给你63元,让你全部换成硬币,求出最小硬币数量,也就是说,怎么用最少的硬币数凑成63元. 分析问题解决这个问题,我们可以将这个大问题分成若干个小问题,自下而上解决问题. 1元对应的最小硬币数是1 2元对应的最小硬币数是2 3元对应的最小硬币数是3 4元对应的最小硬币数是4 -- 63元对应的最小硬币数是XXX 假设我们将前边计算出的金额对应的最小硬币数像
python动态规划算法实例详解

如果大家对这个生僻的术语不理解的话,那就先听小编给大家说个现实生活中的实际案例吧,虽然现在手机是相当的便捷,还可以付款,但是最初的时候,我们经常会使用硬币,其中,我们如果遇到手中有很多五毛或者1块钱硬币,要怎么凑出来5元钱呢?这么一个过程也可以称之为动态规划算法,下面就来看下详细内容吧. 从斐波那契数列看动态规划斐波那契数列:Fn = Fn-1 + Fn-2 ( n = 1,2 fib(1) = fib(2) = 1) 练习:使用递归和非递归的方法来求解斐波那契数列的第 n 项代码如下: #

C++动态规划算法实现矩阵链乘法

相关推荐

随机推荐