精华内容
下载资源
问答
  • 动态规划备忘录算法

    千次阅读 2016-05-13 14:30:33
    备忘录算法是用C[i,j]记录下目前已经”走过的路” 动态规划是自底而上的根据重复次数”走路”的一种规律?

    备忘录算法是用C[i,j]记录下目前已经”走过的路”
    动态规划是自底而上的根据重复次数”走路”的一种规律?

    展开全文
  • 在我们的课程设计、大作业中会涉及到挖金矿问题,今天我用备忘录算法解决,可以得到最优解,便于帮助你们。 //有一个国家发现了5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。 //参与挖矿工人的...

    挖金矿问题-动态规划-备忘录算法(最优解)

    在我们的课程设计、大作业中会涉及到挖金矿问题,今天我用备忘录算法解决,可以得到最优解,便于帮助你们。
    在这里插入图片描述
    //有一个国家发现了5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。
    //参与挖矿工人的总数是10人。
    //每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。
    //要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?
    /*
    500金/5人 200/3 300/4 350/3 400/5
    /
    /

    总容量:10人
    可选量:5人
    n=10,c=5;
    表前i座金山占用j人所拥有的最大黄金
    状态转移方程
    1.j>wi
    F(i,j)=F(i-1,j);
    2.j<=wi
    F(i,j)=max(F(i-1,j),F(i-1,j-wi)+vi);
    */

    在这里插入代码片
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
    typedef struct node{
     int w;
     int v;
    } Node;
    Node Moun[6];
    Node Orign[6];
    int c=10,n=5;
    bool cmp(Node a,Node b){
     if(a.v==b.v)
      return a.w<b.w;
     return a.v>b.v;
    }
    void copy(){
     for(int i=1;i<=n;i++){
      Orign[i].w=Moun[i].w;
      Orign[i].v=Moun[i].v;
     }
    }
    int main(){
     int F[6][11];//备忘录
     int book[6];//标记选取的金山
     int w[6],v[6];
     //初始化
     memset(F,0,sizeof(F));
     memset(book,0,sizeof(book));
     //存入数据 500金/5人    200/3 300/4 350/3 400/5
     Moun[1].v=500,Moun[1].w=5;
     Moun[2].v=200,Moun[2].w=3;
     Moun[3].v=300,Moun[3].w=4;
     Moun[4].v=350,Moun[4].w=3;
     Moun[5].v=400,Moun[5].w=5;
     //复制原金山位置,方便以后求最优解
     copy();
     //按比率排序
     sort(Moun+1,Moun+n+1,cmp);
     //自底向上更新备忘录,找最优值
     for(int i=1;i<=n;i++){
      for(int j=1;j<=c;j++){
       if(Moun[i].w<=j){
        F[i][j]=max(F[i-1][j],F[i-1][j-Moun[i].w]+Moun[i].v);
       }else{
        F[i][j]=F[i-1][j];
       }
      }
     }
     //自顶向下 求最优解
     int tmp=10;
     int k=0;
     for(int i=n;i>=1;i--){
      if(F[i][tmp]!=F[i-1][tmp]){//不相同说明放入
       book[k++]=i; 
      }else{
       tmp-=Orign[i].w;
      }
     }
     //输出最优质值
     cout<<"输出最优质值:"<<endl;
     cout<<F[5][10]<<endl;
     //输出最优解
     cout<<"输出最优解:"<<endl;
     for(int i=0;i<k;i++){
      cout<<"第"<<book[i]<<"座金山"<<endl;
     }
     return 0;
    }
    

    结果:

    输出最优质值:
    900
    输出最优解:
    第2座金山
    第1座金山

    希望可以帮助到你们!

    展开全文
  • 备忘录算法

    2014-03-22 15:51:42
    这是一个用C++做备忘录算法,备忘录方法是动态规划方法的变形。与动态规划算法不同的是,备忘录方法的递归方式是自顶向下的,而动态规划算法则是自底向上的
  • 动态规划解题思路 矩阵链构造函数:构造m[][]和s[][] m中存储的值是计算出来的最小乘法次数,比如m[1][5]就是A1A2A3A4A5的最小乘法次数 s中存储的是获取最小乘法次数时的断链点,s[1][5]对应的就是如何拆分A1A2A3A4...

    问题描述

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

    动态规划解题思路

    矩阵链构造函数:构造m[][]和s[][]
    m中存储的值是计算出来的最小乘法次数,比如m[1][5]就是A1A2A3A4A5的最小乘法次数
    s中存储的是获取最小乘法次数时的断链点,s[1][5]对应的就是如何拆分A1A2A3A4A5,
    比如s[1][5]=3可表示:(A1A2A3)(A4A5),当然内部断链还会继续划分A1A2A3

    public static void matrixChain(int []p,int [][]m,int [][]n){
    	int n=p.length-1;
    	for(int i=1;i<=n;i++)
    		m[i][i]=0;//初始化存储矩阵链的数组对角线
    				  //矩阵链中只有一个矩阵时,次数为0,注意m[0][X]是未使用的
    	for(int r=2;r<=n;r++){//矩阵链长度,长度从2开始
    		for(int i=i;i<=n-r+1;i++){//根据矩阵链长度,控制链的最大起始点
    			int j=i+r+1;//定义矩阵链的末尾矩阵
    			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//向右开始矩阵相乘
    			s[i][j]=i;//存储最佳矩阵链断点
    			for(int k=i+1;k<j;k++){ //这里面将断链点从i+1开始,可以断链的点直到j-1为止
    				int t=m[i][k]+m[k+1][j]+p[p-1]*p[k]*p[j];
    				if(t<m[i][j]){
    					m[i][j]=t;
    					s[i][j]=k;
    				}
    			}
    		}
    	}
    }
    

    备忘录解题思路

    初始化定义相同,唯一不同是,m矩阵存储备忘录数据,存放子问题答案数据

    public static int memoizedmatrixChain(int n){
    	for (int i=0;i<=n;i++){
    		for(int j=0;j<=n;j++){
    			m[i][j]=0;
    		}
    	}//初始化备忘录数组
    	return lookupChain(l,n);
    }
    public static lookupChain(int i,int j){
    	if(m[i][j]>0)
    		return m[i][j];//如果该项子问题有记录,返回该记录
    	if(i==j)
    		return 0;//如果相乘的两个矩阵相等,则返回0
    	int u=lookupChain(i+1,j)+p[i-1]*p[i]p[j];//递归调用
    	s[i][j]=i;//存储最佳断点
    	for(int k=i+1;k<j;k++){//这里面将断点从i+1开始,可以断链的点直到j-1为止
    		int t=lookupChain(i,k)+lookupChain(k+1,j)+p[i-1]*p[k]*p[j];
    		if(t<u){
    			u=t;
    			s[i][j]=k;
    		}
    	}
    	m[i][j]=u;
    	return u;
    }
    

    两种算法对比

    动态规划算法是依次求解矩阵链,最终求解出答案
    备忘录算法是构造一个二维数组,表示任意两个矩阵的关系,数组存储两个矩阵相乘的值,后续如果计算时遇到已经求解出答案的两个矩阵,便可以直接从备忘录中取值,减少计算时间

    展开全文
  • 这里利用备忘录算法对求解过的子问题进行备份存储,避免了相同子问题的重复求解。LCS问题子问题的递归关系式如下: 具体代码实现如下: 1: static int LCS_Memo(int[][] c,char[] X,char[] Y,int i,int j...

    LCS问题是常见的可利用动态规划算法进行解决的问题。这里利用备忘录算法对求解过的子问题进行备份存储,避免了相同子问题的重复求解。LCS问题子问题的递归关系式如下:

    具体代码实现如下:

       1: static int LCS_Memo(int[][] c,char[] X,char[] Y,int i,int j)  
       2:     {  
       3:         if( (i == 0) || (j == 0) )  
       4:             c[i][j]=0;  
       5:         else if(X[i-1] == Y[j-1])  
       6:             c[i][j]=LCS_Memo(c,X,Y,i-1,j-1)+1;  
       7:         else  
       8:         {  
       9:             int p=LCS_Memo(c,X,Y,i-1,j);  
      10:             int q=LCS_Memo(c,X,Y,i,j-1);  
      11:             if(p >= q)  
      12:                 c[i][j]=p;  
      13:             else  
      14:                 c[i][j]=q;  
      15:         }            
      16:         return c[i][j];  
      17:     }  
      18:     
      19:     static int LCS_Length(int[][] c,char[] X,char[] Y)  
      20:     {  
      21:         int m=X.length;  
      22:         int n=Y.length;  
      23:         return LCS_Memo(c,X,Y,m,n);  
      24:     }  
      25:     
      26:     static void printC(int[][] c) {
      27:         // TODO Auto-generated method stub
      28:         for (int i = 1; i < c.length; i++) {
      29:             for (int j = 1; j < c.length; j++) {
      30:                 System.out.print(c[i][j] + "\t");
      31:             }
      32:             System.out.println();
      33:         }
      34:     }
      35:     /**
      36:      * @param args
      37:      */
      38:     public static void main(String[] args) {
      39:         // TODO Auto-generated method stub
      40:         String X = "BCDB";
      41:         String Y = "ABCBDAB";
      42:         char[] x = X.toCharArray();
      43:         char[] y = Y.toCharArray();
      44:         
      45:         int MAX = x.length>y.length?x.length+1:y.length+1;
      46:         int[][] c = new int[MAX][MAX];
      47:         System.out.println(LCS_Length(c,x,y));
      48:         printC(c);        
      49:     }

    转载于:https://www.cnblogs.com/ttltry-air/archive/2012/07/30/2615621.html

    展开全文
  • // #include "stdafx.h" #include #include #include //#include #define V 64// total volume 不一定恰好能放得下,可能有剩余的... cout备忘录算法实现"; memo_fun(); system("pause"); return 0; }
  • 使用备忘录方法解决0-1背包问题: 1.跟直接递归很相似,该算法能将递归遇到的子问题的解保存在一个表中,以便下一个递归遇到同样的子问题时快速求解。...3.备忘录算法动态规划算法的区别有:
  • 动态规划备忘录

    千次阅读 2015-11-04 21:04:58
    动态规划与分治方法相似,都是通过组合子问题的解来求解原文题。分治方法将问题划分为互不相交的子问题,递归地...而动态规划算法对每个子子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都
  • 通常动态规划以自底向上的方式来利用最优子结构,而备忘录方法采取自顶向下的策略   #include using namespace std; #define lengthx 29 #define lengthy 28 int LOOKUP_CHAIN(char *x,char *y,int i,int j...
  • 备忘录动态规划算法的变形﹒备忘录方法也是用表格保存已解决子问题的答案﹒ 与动态规划算法不同的是,备忘录方法的递归方式是自顶向下的,而动态规划算法则是自底向上递归的.因此,备忘录方法的控制结构与直接递归...
  • 备忘录算法(topdown) 递归时代记忆化搜索步骤: m[i][j] 记录 i 到 j 的最优结果,初始化为-1; //min_matrix_OP_beiwanglu #include <iostream> #include <stdio.h> #include <string.h&g...
  • 动态规划备忘录的LCS实现 动态规划从下到上积累能量,中间值全部记录以方便后期计算时调用,但有些时候很多记录的值用不到,这个时候备忘录方法则更好,可以减少记录的值,其特点是自上到下,记录少部分值。以LCS...
  • 分治、动态规划备忘录的区别

    千次阅读 2017-10-11 11:25:15
    最近学算法分析,遇到一个很头疼的问题,分治,动态规划备忘录搞不清,遇到问题不知道应该用什么样的方法合适,查阅很多资料后根据我的理解整理一下。 分治:分治算法对问题进行分解时所遵循的原则是将待求解问题...
  • 矩阵连乘积动态规划备忘录方法Java实现,使用了两种算法实现,并且使用了改进了动态规划算法备忘录方法以自顶向下的方法实现
  • 动态规划算法 #include &lt;iostream&gt; using namespace std; const int N=6; int p[]={30,35,15,5,10,20,25}; int m[N+1][N+1]; int s[N+1][N+1]; void matrixChain(int *p,int m[][N+1],int s[][N+1...
  • 算法-动态规划 Dynamic Programming--从菜鸟到老鸟

    万次阅读 多人点赞 2017-07-15 22:58:29
    前言最近在牛客网上做了几套公司的真题,发现有关动态规划(Dynamic Programming)算法的题目很多。相对于我来说,算法里面遇到的问题里面感觉最难的也就是动态规划(Dynamic Programming)算法了,于是花了好长时间...
  • 关于动态规划备忘录方法的总结

    千次阅读 2013-11-06 21:32:52
    备忘录算法  a. 动态规划的基础是最优子结构———若一个大问题可以划分成多个小问题,则在这多种划分中,必有一种划分,可使得作为宏观问题,这种划分得到的效果最优;而在每个划分出的子问题中,每个子问题也...
  • 算法_备忘录算法_Ackermann函数

    千次阅读 2016-04-08 12:23:43
    Ackermann函数定义如下: 若m=0,返回n+1。 若m>0且n=0,返回Ackermann(m-1,1)。 若m>0且n>0,返回Ackermann(m-1,Ackermann(m,n-1))。import java.util.Scanner;public class Main { private static int[][] A;...
  • 计算矩阵连乘积的备忘录算法 #include #include #define NUM 51 int n; int p[NUM]; int m[NUM][NUM]; int s[NUM][NUM]; //备忘录算法 int LookupChain(int i,int j) { if(m[i][j]>0) returnm[i][j];
  • 大家都知道,数值稍大的递归运行时间对于开发者来说就是场灾难,我们总是想方设法在优化递归,或者说不用递归,此文中从空间时间角度详细剖析以上三种算法的区别,以及运行原理,以斐波那契数为例, 编程语言java ...
  • 分治,动态规划备忘录搞不清,遇到问题不知道应该用什么样的方法合适? 分治:分治算法对问题进行分解时所遵循的原则是将待求解问题分解为若干个规模较小、相互独立且与原问题相同的子问题(不包含公共的子问题...
  • 动态规划备忘录方法的区别 动态规划算法的基本要素: 1 最优子结构性质 当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。 2 重叠子问题性质 动态规划算法对每个问题只解一次,将其解保存在...
  • 对比备忘录方法(递归)和动态规划(递推) 备忘录方法 备忘录方法要用递归实现 递归是自顶向下的解决问题的:即从目标开始,将问题划分,对子问题求解,直到边界 递归前对备忘录进行查询,当前备忘录未被填写时,...
  • 动态规划中的 循环结构可以通过递归的方式实现,但是单纯的递归方法每次都会将已计算过的子问题重新计算,时间复杂度较高,因此可以通过在递归中做备忘录的方法建设时间复杂度。具体见代码: #include using ...
  • //矩阵连乘的动态规划算法 #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 ...
  • 这个是《算法设计与分析》王晓东版的上面的矩阵连乘的动态规划法和备忘录法的实现,是用C++编写的
  • LCS的做备忘录算法

    2014-07-07 14:29:19
    算法思想:自顶向下的做备忘录,递归 */ #include #include using namespace std; string x,y; int c[100][100]; int b[100][100]; int inf = 0x7fff; //int最大2^15-1 //int xx,yy; //特别注意!!递归函数内部...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,563
精华内容 10,625
关键字:

动态规划备忘录算法