精华内容
下载资源
问答
  • 备忘录方法

    2021-03-24 21:22:47
    因此,备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相同子问题的重复求解。 UML如下: 具体代码实现: 成绩单: public class ...

    定义:

    备忘录方法也用一个表格来保存已解决的子问题的答案,在下次需要解决此问题时,只要简单地查看该子问题的解答,而不必重新计算。与动态规划算法不同的是,备忘录方法的递归方式是自顶向下的,而动态规划算法则是自底向上递归的。因此,备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相同子问题的重复求解。

    UML如下:

    在这里插入图片描述

    具体代码实现:

    成绩单:

    public class Originator {
    private String state;         //成绩
    public void setState(String state) {
    	this.state = state;
    }
    public String getState() {
    	return state;
    }
    public Memento Create() {     //创造备忘录
    	return new Memento(state);
    }
    public void SetMemento(Memento memento) {     //还原
    	this.state=memento.getState();
    }	
    public void show() {
    	System.out.println("当前分数"+state);
    }
    }
    

    备忘录:

    public class Memento {
    public String state;
    public Memento(String state) {
    	this.state=state;
    }
    public String getState() {
    	System.out.println("正在还原");
    	return state;
    }
    }
    

    管理者:

    public class Administration {
    private Memento memento;          //备忘录
    public void setMemento(Originator originator) {
    	this.memento = originator.Create();
    }
    public Memento getMemento() {
    	return memento;
    }
    }
    

    主方法:

    public class Main {
    
    	public static void main(String[] args) {
    		Originator originator=new Originator();
    		originator.setState("111");
    		originator.show();
    		Administration a=new Administration();
    		a.setMemento(originator);//设置备忘录
    		originator.setState("321");;
    		originator.show();
    		originator.SetMemento(a.getMemento());//还原数据
    		originator.show();
            
    	}
    
    }
    
    展开全文
  • 要求:给定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;
    }
    

    运行结果:

    展开全文
  • 求解整数拆分问题 一、【问题描述】 求将整数无需拆分为最大数为k(称为n的k拆分)的拆分方案个数,要求所有的拆分方案不重复 二、【问题求解】 设n=5,k=5,对应的拆分方案有 ①5=5 ②5=4+1 ③5=3+2 ④5=3+1+1 ⑤5=...

    求解整数拆分问题

    一、【问题描述】
    求将整数无需拆分为最大数为k(称为n的k拆分)的拆分方案个数,要求所有的拆分方案不重复

    二、【问题求解】
    设n=5,k=5,对应的拆分方案有
    ①5=5
    ②5=4+1
    ③5=3+2
    ④5=3+1+1
    ⑤5=2+2+1
    ⑥5=2+1+1+1
    ⑦5=1+1+1+1+1
    该题适合用动态规划求解,设f(n,k)为n的k拆分的拆分方案个数:

    (1)当n=1,k=1时,显然f(n,k)=1
    (2)当n<k时,有f(n,k)=f(n,n)
    (3)当时,其拆分方案有将拆分成1个的拆分方案,以及n的n-1的拆分方案,前者仅仅一种,所以有f(n,n)=f(n,n-1)+1.
    (4)当n>k时,根据拆分方案中是否包含k,可分为两种情况。
    ①拆分中包含k的情况:即一部分为单个k,另一部分为{x1,x2,…,xi},后者的和为n-k,后者中可能再次出现k,因此是(n-k)的k拆分,所以这种拆分方案个数为f(n-k,k)。
    ②拆分中不包含k的情况:则拆分中所有拆分数都比k小,即n的(k-1)拆分,拆分方案个数为f(n,k-1)
    因此,f(n,k)=f(n-k,k)+f(n,k-1)

    状态方程
    完整程序(以n=5,k=5为例)
    解法1:

    #include<iostream>
    using namespace std;
    int dp[100][100];  //动态规划数组 
    void split(int n,int k)  //求解算法
    {
    	for(int i=1;i<=n;i++)
    	for(int j=1;j<=k;j++){
    		if(i==1||j==1)
    		dp[i][j]=1;
    		else if(i<j)
    		dp[i][j]=dp[i][i];
    		else if(i==j)
    		dp[i][j]=dp[i][j-1]+1;
    		else
    		dp[i][j]=dp[i][j-1]+dp[i-j][j];
    	}
     } 
     int main(){
     	int n,k;
     	n=5;
    	k=5;
    	split(n,k);
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=k;j++){
    			cout<<dp[i][j]<<" ";
    		}
    		cout<<endl;
    	}
    	return 0;
     }
    

    解法2:

    #include<iostream>
    using namespace std;
    int dp[100][100]={0};  //动态规划数组 
    int split(int n,int k)  //求解算法
    {
    	if(dp[n][k]!=0) return dp[n][k];
    	if(n==1||k==1){
    		dp[n][k]=1;
    		return dp[n][k];
    	}
    	else if(n<k){
    		dp[n][k]=split(n,n);
    		return dp[n][k];
    	}
    	else if(n==k){
    		dp[n][k]=split(n,k-1)+1;
    		return dp[n][k];
    	}
    	else{
    		dp[n][k]=split(n,k-1)+split(n-k,k);
    		return dp[n][k];
    	}
     } 
     int main(){
     	int n,k;
     	n=5;
    	k=5;
    	cout<<split(n,k)<<endl;
    	return 0;
     }
    

    ps:在此解法中设置数组dp[n][k]存放f(n,k),首先初始化dp的所有元素为0,当dp[n][k]不为0时候表示对应的子问题已经求解,直接返回结果,这种方法是一种递归算法,其执行过程是自顶向下的,当某个子问题求出后,将其结果存放在一张表中,这也称为备忘录方法。备忘录方法时动态规划的变形,与动态规划算法不同的是,备忘录方法的递归方式时自顶向下的,二动态规划算法时自底向上的。

    展开全文
  • 某推销员要从城市v1出发,访问其它城市v2,v3,…,v6各一次且仅一次,最后返回v1。D为各城市间的距离矩阵。 问:该推销员应如何选择路线,才能使总的行程最短?
  • 1. 动态规划是自底向上 ,备忘录方法是自顶向下。 2、动态规划每个子问题都要解一次,但不会求解重复子问题;备忘录方法只解哪些确实需要解的子问题;递归方法每个子问题都要解一次,包括重复子问题。 转载于:...

    1. 动态规划是自底向上 ,备忘录方法是自顶向下。

    2、动态规划每个子问题都要解一次,但不会求解重复子问题;备忘录方法只解哪些确实需要解的子问题;递归方法每个子问题都要解一次,包括重复子问题。

    转载于:https://www.cnblogs.com/linyx/p/4003387.html

    展开全文
  • 算法作业-Ackermann函数-备忘录方法

    千次阅读 2018-06-03 14:51:58
    Ackermann函数定义如下:1,请采用备忘录方法设计一个求解该函数的递归算法。2,请用动态规划方法设计一个非递归求解算法,该算法由两个嵌套循环组成,只能使用O(m)内的空间。解法一:备忘录方法使用一个二维数组A[m]...
  • 动态规划&备忘录方法&递归方法

    千次阅读 2015-10-29 21:08:39
    动态规划的基本思想是,将原问题拆分为若干子问题,自底向上的求解...备忘录方法,采用的也是自顶向下的思想,但是该方法维护了一个记录子问题解的表,虽然填表动作的控制结构更像递归方法,但是的确避免了子问题的重复
  • 在之前的文章中,我们学习了如何用动态规划算法实现矩阵的连乘积问题,由于矩阵连乘积...这样就可以得到一个基于递归算法的高效方法,即备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备...
  • 使用备忘录方法解决0-1背包问题: 1.跟直接递归很相似,该算法能将递归遇到的子问题的解保存在一个表中,以便下一个递归遇到同样的子问题时快速求解。 2.为了区分一个子问题是否已经求解,可以通过查表的方式来...
  • 备忘录方法为每个子问题建立一个记录项,初始化时,该记录项存入一个特殊值,表示该子问题尚未解决。在求解过程中,对每个待求子问题,首先查看其相应的记录项。有变化则不算,无则算。 代码如下:public class ...
  • 相同点:其基本思想都是将待求解问题分解为若干子问题,先求解子问题,再结合这些子问题的解得到原问题的解。 差异点:与分治法不同的是,适合用动态规划法求解的问题经分解得到的子问题往往不是相互独立的。有些...
  • 备忘录方法——动态规划法的变形    e.g. 求LCS的问题。当xi=yj时,求C[i,j]只需知道C[i-1,j-1] 而无需用到C[i,0]~C[i,j-1]及C[i-1,j]~C[i-1,n]。 ∴ 当只需求出一个LCS时, 可能有一些C[p,q]在整个求解...
  • 因此,备忘录方法的控制结构与直接递归方法的控制结构相同,而区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相同子问题的重复求解备忘录方法为每个子问题建立一个记录项,并初始化为...
  • 相同点:其基本思想都是将待求解问题分解为若干子问题,先求解子问题,再结合这些子问题的解得到原问题的解。 差异点:与分治法不同的是,适合用动态规划法求解的问题经分解得到的子问题往往不是相互独立的。有些...
  • 备忘录法的控制与直接使用递归方法的控制结构相同。 备忘录法又称记忆化搜索,自顶向下的方式解决问题。 备忘录法的实现 避免子问题重复被求解,我们可以定义一个数组,每次要计算一个子问题时,首先从数组中查询...
  • 对比备忘录方法(递归)和动态规划(递推) 备忘录方法 备忘录方法要用递归实现 递归是自顶向下的解决问题的:即从目标开始,将问题划分,对子问题求解,直到边界 递归前对备忘录进行查询,当前备忘录未被填写时,...
  • 分别使用分治、记忆化搜索和递推三种方法完成数字金字塔 使用bfs计算图形面积 编程语言选用C++
  • POJ 1159(dp+备忘录

    2018-04-06 00:30:06
    不用备忘录方法会引起TLE 但基本思路还是如下: 递归求解。 也可以用动态规划算法,但我看了半天还是不好理解,都说的不是特别好,要是有哪位大牛有好的思路希望在评论区给予我帮助,感激不尽。 #include&lt...
  • 数位dp备忘录

    2016-03-15 18:28:00
    hdu 4734:把限制值化为数组形式,逐位求解 hdu 4507:类似于上题,其中求平方和的方法很妙 SPOJ BALNUM Balanced Numbers:经典数位dp,注意两点,1,不要把前导0的0记录进去了,如09,实际应该是9,0没有出现过。2...
  • 前言 ...因此,本题主要还是想推荐一个新的思路:备忘录。分析原题目,发现有效的w(a,b,c)只在0≤a,b,c≤200\le a,b,c \le200≤a,b,c≤20范围内有效,所以用一个w[21][21][21]w[21][21][21]w[21][21]
  • 分治、动态规划,备忘录的区别

    千次阅读 2017-10-11 11:25:15
    最近学算法分析,遇到一个很头疼的问题,分治,动态规划,备忘录搞不清,遇到问题不知道应该用什么样的方法合适,查阅很多资料后根据我的理解整理一下。 分治:分治算法对问题进行分解时所遵循的原则是将待求解问题...
  • 动态规划之备忘录

    千次阅读 2015-11-04 21:04:58
    动态规划与分治方法相似,都是通过组合子问题的解来求解原文题。分治方法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,求出原问题的解。与之相反,动态规划应用于子问题重叠的情况,即...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 127
精华内容 50
关键字:

备忘录方法求解