精华内容
下载资源
问答
  • 2021-03-15 11:06:21

    //矩阵连乘的动态规划算法

    #include

    using namespace std;

    long MaxtrixChain1(int n);

    long MaxtrixChain1(int i, int j);

    int const MAX = 1000;

    long subMatrixChain[MAX][MAX];

    int bestK[MAX][MAX];

    int dim[MAX];

    int main()

    {

    int i, n;

    while (cin >> n)

    {

    for (i = 0; i <= n; i++)

    {

    cin >> dim[i];

    }

    cout << MaxtrixChain1(n);

    memset(subMatrixChain,-1,sizeof(subMatrixChain));

    //cout << endl << subMatrixChain[5][1];

    cout << "case 2:" << MaxtrixChain1(1,n);

    }

    return 0;

    }

    long MaxtrixChain1(int n)

    {

    int i,j,k,len;

    for (i = 1; i <= n; i++)

    {

    subMatrixChain[i][i] = 0;

    }

    for (len = 2; len <= n; len++)

    {

    for (i = 1; i <= n - len + 1; i++)

    {

    j = i + len - 1;

    subMatrixChain[i][j] = 100000000;

    for (k = i; k < j; k++)

    {

    long ans = subMatrixChain[i][k] + subMatrixChain[k+1][j] + dim[i-1] * dim[k] * dim[j];

    if (ans < subMatrixChain[i][j])

    {

    subMatrixChain[i][j] = ans;

    bestK[i][j] = k;

    }

    }

    }

    }

    return subMatrixChain[1][n];

    }

    long MaxtrixChain1(int i,int j)

    {

    if (subMatrixChain[i][j] != -1)

    {

    return subMatrixChain[i][j];

    }

    if (i == j)

    {

    subMatrixChain[i][j] = 0;

    return 0;

    }

    long ans,max1 = 10000000;

    for (int k = i; k < j; k++)

    {

    ans = MaxtrixChain1(i,k)+ MaxtrixChain1(k+1,j)+ dim[i-1] * dim[k] * dim[j];

    if (ans < max1)

    {

    max1 = ans;

    bestK[i][j] = k;

    }

    }

    subMatrixChain[i][j] = max1;

    return max1;

    }

    更多相关内容
  • 备忘录表与标记函数表算法的复杂度分析算法的迭代实现伪代码描述迭代实现的源代码运行结果截图结束语 问题描述 给定递增有序的元素序列S=⟨a1,a2,⋯ ,an⟩S=\left \langle a_1,a_2,\cdots,a_n\right \rangleS=⟨a1...

    问题描述

    给定递增有序的元素序列 S = ⟨ a 1 , a 2 , ⋯   , a n ⟩ S=\left \langle a_1,a_2,\cdots,a_n\right \rangle S=a1,a2,,an与相关存取概率分布 C = ⟨ q ( 0 ) , p ( 1 ) , q ( 1 ) , p ( 2 ) , q ( 2 ) , ⋯   , p ( n ) , q ( n ) ⟩ C=\left \langle q(0), p(1), q(1), p(2), q(2), \cdots, p(n), q(n) \right \rangle C=q(0),p(1),q(1),p(2),q(2),,p(n),q(n),将这些元素存储在一棵二叉树的结点上,以查找 x x x是否在这些数中。如果 x x x不在,确定 x x x在哪个空隙。设法构造一棵最优二叉搜索树使得平均查找次数 t t t最小。一棵二叉搜索树的平均查找次数定义如下:
    t = ∑ i = 1 n p ( i ) ( 1 + d ( i ) ) + ∑ j = 0 n q ( j ) d ( j ) t=\sum_{i=1}^{n}{p(i)(1+d(i))}+\sum_{j=0}^{n}{q(j)d(j)} t=i=1np(i)(1+d(i))+j=0nq(j)d(j)
    其中, d ( i ) d(i) d(i)表示结点 a i a_i ai的深度, i = 1 , 2 , ⋯   , n i=1,2,\cdots, n i=1,2,,n d ( j ) d(j) d(j)表示空隙(叶子)结点 ( a j , a j + 1 ) (a_j, a_{j+1}) (aj,aj+1)的深度, j = 0 , 1 , ⋯   , n j=0,1,\cdots, n j=0,1,,n

    问题建模

    1.子问题的边界参数化

    S [ i , j ] = < x i , x i + 1 . . . x j > S[i,j]=<x_i,x_{i+1}...x_j> S[i,j]=<xi,xi+1...xj> S S S i i i j j j作为边界的子数据集, C [ i , j ] = < a i − 1 , b i , a i , . . . , b j , a j > C[i,j]=<a_{i-1},b_i,a_i,...,b_j,a_j> C[ij]=<ai1,bi,ai,...,bj,aj>是对应 S [ i , j ] S[i,j] S[i,j]存取概率分布。
    子问题划分:以 x k x_k xk作为根划分成两个子问题
    S [ i , k − 1 ] , C [ i , k − 1 ] S[i,k-1],C[i,k-1] S[i,k1],C[ik1]
    S [ k + 1 , j ] , C [ k + 1 , j ] S[k+1,j],C[k+1,j] S[k+1,j],C[k+1j]

    2.递推关系

    设m[i,j]是相对于输入S[i,j]和C[i,j]的最优二叉搜索树的平均比较次数,令 w [ i , j ] = ∑ p = i − 1 j a p + ∑ q = i j b q w[i,j]=\sum_{p=i-1}^ja_p+\sum_{q=i}^jb_q w[i,j]=p=i1jap+q=ijbq是C[i,j]中所有概率(包括数据元素与空隙)之和,则递推方程为
    { m [ i , j ] = min ⁡ { m [ i , k − 1 ] + m [ k + 1 , j ] + w [ i , j ] } if  1 ≤ i ≤ j ≤ n m [ i , i − 1 ] = 0 if  i = 1 , 2 , . . . n \begin{cases} m[i,j]=\min \{m[i,k-1]+m[k+1,j]+w[i,j]\} &\text{if } 1\leq i\leq j \leq n \\ m[i,i-1]=0 &\text{if } i=1,2,...n \end{cases} {m[i,j]=min{m[i,k1]+m[k+1,j]+w[i,j]}m[i,i1]=0if 1ijnif i=1,2,...n

    3.备忘录表与标记函数表

    w:最优二叉搜索树的权;

    m:计算最优二叉搜索树的成本;

    r:最优二叉搜索树的根。

    算法的复杂度分析

    i , j i,j i,j的所有组合 O ( n 2 ) O(n^2) O(n2)种,每种要对不同的k进行计算, k = O ( n ) k=O(n) k=O(n)每次计算为常数时间 T ( n ) = O ( n 3 ) , S ( n ) = O ( n 2 ) T(n)=O(n^3),S(n)=O(n^2) T(n)=O(n3),S(n)=O(n2)

    算法的迭代实现伪代码描述

     function BST(p, q, n)
     	let m[1...n+1,0...n],w[1...n+1,0...n] and r[1...n,1...n] be new tables
     	for i = 1 → n + 1 do
    		m[i, i − 1] ← 0
     		w[i, i − 1] ← qi−1
     	for l = 1 → n do
     		for i = 1 → n − l + 1 do
     			j ← i + l − 1
    			m[i, j] ← ∞
     			w[i, j] ← w[i, j − 1] + pj + qj
     			for r = i → j do
     				t ← m[i, r − 1] + m[r + 1, j] + w[i, j]
     				if t < m[i, j] then
     					m[i, j] ← t
     					r[i, j] ← r
     	return m, r
     end function
    

    迭代实现的源代码

    #include<iostream>
    #include<vector>
    using namespace std;
    int main(){
    	int n;
    	cin >> n;
    	vector<int> S,C;
    	vector<vector<int> > w,m,r;//定义备忘录表 
    	vector<int> B;
    	for(int i = 1;i <= n;i ++){
    		int a;
    		cin >> a;
    		S.push_back(a);
    	}//输入集合S 
    	for(int i = 0;i < 2*n+1;i ++){
    		double a;
    		cin >> a;
    		C.push_back(100*a);
        }//输入存取概率,乘以100 
    	for(int j = 0;j <= n+1;j++){
    		B.push_back(0);
    	}
    	for(int i = 0;i <= n+1;i++){	
    		m.push_back(B);
    		w.push_back(B);
    		r.push_back(B);
    	}
    	for(int i = 1;i <= n+1;i ++){
    		m[i][i-1] = 0;
    		w[i][i-1] = C[2*(i-1)];
    	}//初始化备忘录表
    	for(int l = 1;l <= n;l ++){
    		for(int i = 1;i <= n-l+1;i ++){
    			int j = i+l-1;
    			m[i][j] = 2147483647;
    			w[i][j] = w[i][j-1] + C[2*j-1] + C[2*j];
    			for(int root = i;root <= j;root ++){
    				int t = m[i][root-1] + m[root+1][j] + w[i][j];
    				if(t < m[i][j]){
    					m[i][j] = t;
    					r[i][j] = root;
    				}
    			}
    		}
    	}//利用备忘录法迭代实现构造最优二叉搜索树 
    	for(int i = 1;i <= n;i ++){
    		for(int j = 1;j <= n;j ++){
    			cout << r[i][j] << " ";
    		}
    		cout << endl;
    	}//输出记录根节点的表 
    	cout << "最小代价为" << (double)m[1][n]/100; 
    	return 0;//输出最小期望代价 
    }
    

    运行结果截图

    在这里插入图片描述

    结束语

    没有明确表达的爱意都是错觉

    作者:花城

    展开全文
  • 要求:给定n个矩阵构成的序列{A1,A2,……,An},对乘积A1,A2,……,An,找出最小化乘法次数的加括号方法。 1.建立递归关系,确定矩阵连乘的最优子结构 代码: //计算该连乘式子的最佳结合方式 int Matrix...

    问题:给定n个矩阵{A1,A2,……An},其中Ai与Ai+1是可乘的,i=1,2,……n-1。如何能确定计算矩阵连乘乘积的计算次序,使得一次次序矩阵连乘需要的数乘次数最少。

    要求:给定n个矩阵构成的序列{A1,A2,……,An},对乘积A1,A2,……,An,找出最小化乘法次数的加括号方法。

    1.建立递归关系,确定矩阵连乘的最优子结构

    代码:

    //计算该连乘式子的最佳结合方式
    int MatrixChain(vector<int>& p,int beg, int end)
    {
    	if(m[beg][end]>0) 
    	{
    	   return m[beg][end];
        }
    	if(beg==end) 
    	   return 0;
    	int u = MatrixChain(p,beg,beg) +MatrixChain(p,beg+1,end)+p[beg-1]*p[beg]*p[end];
    	s[beg][end] = beg;
    	for (int K = beg+1; K <end ; K++)
    	{
    		int t = MatrixChain(p,beg,K) + MatrixChain(p,K+1,end) + p[beg-1]*p[K]*p[end]; //递归   
    		if (t<u)
    		{
    			u = t;    //从k点处断开,分别求得每次的数乘次数 
    			s[beg][end] = K;//返回 t,k中较小的值,并记录断点处 k 
    		}
    	}
    	m[beg][end] = u;
    	return u;
    }

    2.输出最优子结构,运用递归加括号

    代码:

    //输出该连乘式子的最佳结合方式
    void PrintMatrixChain(int n,int m)
    {
    	if(n==m)     //只有一个矩阵,直接输出 
    	{
    		cout<<"A"<<n;    
    		return;
    	}
    	int k = s[n][m];             
    	if(n==k)
    		PrintMatrixChain(n,k);      //递归 
    	else
    	{
    		cout<<"(";
    		PrintMatrixChain(n,k);
    		cout<<")";
    	}
    	if(k+1==m)               //两个矩阵 
    		PrintMatrixChain(k+1,m);        //递归 
    	else
    	{
    		cout<<"(";
    		PrintMatrixChain(k+1,m);       //递归,从得到最优解的地方 s[][]处断开 
    		cout<<")";
    	}
    }

    3.矩阵初始化,主函数

    代码:

    int main()
    {
    	vector<int> vec;   //创造一个空的容器 vec 
    	copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(vec));
    	int n = vec.size()-1;//一共有n个矩阵相乘
    	m = vector<vector<int> >(n+1,vector<int>(n+1,0));//0行0列空余
    	s = vector<vector<int> >(n+1,vector<int>(n+1,0));//0行0列空余
    	//初始化m数组
    	for(int i = 0;i<=n;i++) m[i][i] = 0;
    	int u = MatrixChain(vec,1,n);
    	cout<<"最优解为计算"<<u<<"次乘法!"<<endl;
    	PrintMatrixChain(1,vec.size()-1);
    	return 0;
    }

    完整代码:

    #include<iostream>
    #include<vector>
    #include<iterator>
    #include<algorithm>
    using namespace std;
     
    /*
    *矩阵连乘(备忘录方法:自顶向下递归)
    */
    vector<vector<int> > m;//m[i][j]表示矩阵Ai连乘到Aj的最少运算次数
    vector<vector<int> > s;//s[i][j]记录矩阵Ai和矩阵Aj之间的分割点
     
    //计算该连乘式子的最佳结合方式
    int MatrixChain(vector<int>& p,int beg, int end)
    {
    	if(m[beg][end]>0) 
    	{
    	   return m[beg][end];
        }
    	if(beg==end) 
    	   return 0;
    	int u = MatrixChain(p,beg,beg) +MatrixChain(p,beg+1,end)+p[beg-1]*p[beg]*p[end];
    	s[beg][end] = beg;
    	for (int K = beg+1; K <end ; K++)
    	{
    		int t = MatrixChain(p,beg,K) + MatrixChain(p,K+1,end) + p[beg-1]*p[K]*p[end]; //递归   
    		if (t<u)
    		{
    			u = t;    //从k点处断开,分别求得每次的数乘次数 
    			s[beg][end] = K;//返回 t,k中较小的值,并记录断点处 k 
    		}
    	}
    	m[beg][end] = u;
    	return u;
    }
     
    //输出该连乘式子的最佳结合方式
    void PrintMatrixChain(int n,int m)
    {
    	if(n==m)     //只有一个矩阵,直接输出 
    	{
    		cout<<"A"<<n;    
    		return;
    	}
    	int k = s[n][m];             
    	if(n==k)
    		PrintMatrixChain(n,k);      //递归 
    	else
    	{
    		cout<<"(";
    		PrintMatrixChain(n,k);
    		cout<<")";
    	}
    	if(k+1==m)               //两个矩阵 
    		PrintMatrixChain(k+1,m);        //递归 
    	else
    	{
    		cout<<"(";
    		PrintMatrixChain(k+1,m);       //递归,从得到最优解的地方 s[][]处断开 
    		cout<<")";
    	}
    }
    int main()
    {
    	vector<int> vec;   //创造一个空的容器 vec 
    	copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(vec));
    	int n = vec.size()-1;//一共有n个矩阵相乘
    	m = vector<vector<int> >(n+1,vector<int>(n+1,0));//0行0列空余
    	s = vector<vector<int> >(n+1,vector<int>(n+1,0));//0行0列空余
    	//初始化m数组
    	for(int i = 0;i<=n;i++) m[i][i] = 0;
    	int u = MatrixChain(vec,1,n);
    	cout<<"最优解为计算"<<u<<"次乘法!"<<endl;
    	PrintMatrixChain(1,vec.size()-1);
    	return 0;
    }
    

    运行结果:

    展开全文
  • 【算法】备忘录法(记忆化搜索)

    千次阅读 2020-11-11 22:18:52
    备忘录法的控制与直接使用递归方法的控制结构相同。 备忘录法又称记忆化搜索,自顶向下的方式解决问题。 备忘录法的实现 避免子问题重复被求解,我们可以定义一个数组,每次要计算一个子问题时,首先从数组中查询...


    什么是备忘录法

    1. 备忘录法是为了解决避免递归算法中相同子问题的重复求解。
    2. 备忘录法为每个解过的子问题建立备忘录以备需要时查看,所以也称搜表法。
    3. 备忘录法的控制与直接使用递归方法的控制结构相同。
    4. 备忘录法又称记忆化搜索,自顶向下的方式解决问题。

    备忘录法的实现

    1. 避免子问题重复被求解,我们可以定义一个数组,每次要计算一个子问题时,首先从数组中查询这个子问题的解,子问题解没有在数组中,说明没有计算过该子问题,我们可以计算该子问题,并将解放到数组中去,以便下次计算该子问题时,可以直接从数组中拿。

    2. 例如整数划分问题:随着划分整数越大,重复的子问题就越多,为了避免子问题重复计算,我们可以在计算整数划分的算法中添加一个二位数组参数,把我们子问题的解放到数组中,例如q(6,3)的解就放到 d [6] [3]中。

    在这里插入图片描述

    代码实现:

    public class Demo03 {
    
    
        //测试:
        public static void main(String[] args) {
    
            System.out.println(division(6,6,new int[9][9]));
    
        }
    
    
        public static int division(int m,int n,int[][] d){
            //q(1,n)或q(m,1)==1
            if (m==1 || n==1){
                return 1;
            }
    
            //q(m,n)=q(n,n)=q(n,n-1) +1
            if (m == n){
                if (d[m][n] == 0) {
                    d[m][n] = division(n, n-1, d)+1;
                }
                return d[m][n];
            }
    
    
            //m < n  :q(m,n)=q(m,m)
            if (m < n){
                if (d[m][n] == 0) {
                    d[m][n] = division(m, m, d);
                }
                return d[m][n];
            }
    
            //m>n>1时 q(m,n)=q(m,n-1)+q(m-n,n)
            if (m > n && n >1){
                if (d[m][n] == 0) {
                    d[m][n] = division(m, n-1, d)+division(m-n,n,d);
                }
                return d[m][n];
            }
    
            return 0;
        }
    
    
    }
    
    展开全文
  • 动态规划_备忘录法_矩阵链乘问题描述完全加括号最优子结构最优解的递推关系算法描述(伪代码)结束语 问题描述 给定nnn个矩阵{A1,A2,A3,...,An}\{A_1,A_2,A_3,...,A_n\}{A1​,A2​,A3​,...,An​},其中AiA_iAi​为...
  • 带有备忘录的递归算法

    千次阅读 2021-10-31 17:18:05
    } } 2 带备忘录的递归算法 带备忘录的递归算法,子问题个数=树节点数=n,解决一个子问题还是O(1),所以带备忘录的递归算法的时间复杂度是O(n)。接下来呢,我们用带备忘录的递归算法去撸代码,解决这个青蛙跳阶问题的...
  • 备忘录方法 #include using namespace std ; int m[ 7 ][ 7 ],s[ 7 ][ 7 ]; int p[]={ 30 , 35 , 15 , 5 , 10 , 20 , 25 }; const int N= 6 ; int Lookupchain( int i, int j) { if (m...
  • } 两种算法对比 动态规划算法是依次求解矩阵链,最终求解出答案 备忘录算法是构造一个二维数组,表示任意两个矩阵的关系,数组存储两个矩阵相乘的值,后续如果计算时遇到已经求解出答案的两个矩阵,便可以直接从...
  • 动态规划与备忘录方法的区别 动态规划算法的基本要素: 1 最优子结构性质 当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。 2 重叠子问题性质 动态规划算法对每个问题只解一次,将其解保存在...
  • 动态规划&备忘录方法&递归方法

    千次阅读 2015-10-29 21:08:39
    动态规划的基本思想是,将原问题拆分为若干子问题,自底向上的求解...备忘录方法,采用的也是自顶向下的思想,但是该方法维护了一个记录子问题解的表,虽然填表动作的控制结构更像递归方法,但是的确避免了子问题的重复
  • //遍历从i+1开始一直到j的分段方法,找到一个最小的乘法次数时的分段方法,保留下来 if (t [i][j]) { m[i][j] = t; s[i][j] = k; } } } } } void Trace(int i, int j, int **s) { if (i == j) { cout “A” ; } ...
  • 在之前的文章中,我们学习了如何用动态规划算法实现矩阵的连乘积问题,由于矩阵连乘积...这样就可以得到一个基于递归算法的高效方法,即备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备...
  • 参考王晓东《计算机算法设计与分析》(第3版)动态规划章节中的内容
  • 备忘录方法

    千次阅读 2018-08-03 10:56:08
    算法定位 该法是动态规划的变形,或者可以理解为动态规划的优化,优化在增强理解和...以上一篇中的矩阵连乘问题为例,可以得到如下的递归求解套路: public static int recurMatrixChain(int i,int j) { /** ...
  • 件物品只能⽤⼀次,求解将哪些物品装⼊背包⾥物品价值总和最⼤。 示例: 思路: 动态规划五部曲: 1.确定dp数组以及下标的含义 使⽤⼆维数组,即dp[i][j] 表示从下标为[0-i]的物品⾥任意取,放进容量 为...
  • 一共有十级台阶,每一次只能上1级或2级,问一共有多少种上台阶的方法。 解析: 这个问题可以从一阶、两阶、三阶来入手。一阶显然只有一种上法发,两阶则有两种上法,三阶则是一阶和两阶上法的总和。 根据这样的思路...
  • 矩阵连乘问题的介绍网上很多,就不复述了,以下分别用递归算法、动态规划算法和备忘录法实现. 递归算法实现 /******************** Divide-Conquer ********************/ int MatrixChain_Recursive(int i, ...
  • #include<iostream>...*矩阵连乘(备忘录方法:自顶向下递归) */ vector<vector<int> > m;//m[i][j]表示矩阵Ai连乘到Aj的最少运算次数 vector<vector<int> > s;//s[i][j].
  • 使用备忘录方法解决0-1背包问题: 1.跟直接递归很相似,该算法能将递归遇到的子问题的解保存在一个表中,以便下一个递归遇到同样的子问题时快速求解。 2.为了区分一个子问题是否已经求解,可以通过查表的方式来...
  • 动态规划:0-1背包问题(递归+备忘录)
  • 分治,动态规划,备忘录搞不清,遇到问题不知道应该用什么样的方法合适? 分治:分治算法对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互独立且与原问题相同的子问题(不包含公共的子问题...
  • 备忘录是一种行为设计模式,允许在不暴露对象实现细节的情况下保存和恢复对象之前的状态。
  • Java备忘录模式

    2021-04-03 08:06:03
    角色Originator(发起人):负责创建一个备忘录Memento,用以记录当前时刻自身的内部状态,并可使用备忘录恢复内部状态。Originator可以根据需要决定Memento存储自己的哪些内部状态。Memento(备忘录):负责存储...
  • 求解整数拆分问题 一、【问题描述】 求将整数无需拆分为最大数为k(称为n的k拆分)的拆分方案个数,要求所有的拆分方案不重复 二、【问题求解】 设n=5,k=5,对应的拆分方案有 ①5=5 ②5=4+1 ③5=3+2 ④5=3+1+1 ⑤5=...
  • 矩阵连乘备忘录

    2021-05-02 10:05:59
    使用备忘录求解矩阵连乘问题,输出最少乘法次数。 输入 每组数据包括两行,第一行为数组长度n,第二行为存储矩阵维数的一维数组。 输出 矩阵连乘最优计算次数。 样例输入 Copy 7 30 35 15 5 10 20 25 样例输出 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,345
精华内容 1,738
关键字:

备忘录方法求解