精华内容
下载资源
问答
  • 回溯法和动态规划法解01背包问题,控制台应用程序,代码没有编译完成,请自行编译
  • 1) 动态规划法求解问题的一般思路,动态规划法求解本问题的思路及其C/C++程序实现与算法的效率分析。 2) 贪心算法在0-1背包问题求解中的应用 3) 回溯法求解问题的一般思路,回溯法求解本问题的思路及其C/C++程序实现...
  • #define _CRT_SECURE_NO_WARNINGS .../* 动态规划法解决0-1背包问题(使用递推公式进行数据生成) */ /* 定义背包的属性 */ int package_total_contain; //背包的容量 int package_max_value; ...

    使用C语言实现的代码如下所示

    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    
    /*		   动态规划法解决0-1背包问题(使用递推公式进行数据生成)	    	*/
    
    /* 定义背包的属性 */
    int package_total_contain;		//背包的容量
    int package_max_value;			//在不超过背包容量的前提下,放入背包中的物品实现的最大价值
    
    /* 定义物品的属性 */
    int goods_total_num;	  //总的物品的数量
    int *pArrayGoodsWeight;	  //定义一个指针指向存放物品重量的数组
    int *pArrayGoodsValue;	  //定义一个指针指向存放物品价值的数组
    int *pArrayGoodsCount;	  //定义指针指向存放物品是否被选中的数组,选中就置为1,未选中就置为0,与物品一一对应,以此得出选取物品是哪些
    
    /* 函数的声明 */
    void Init();
    int GetMaxValue(int goods_total_num, int package_total_contain, int *pArrayGoodsWeight, int *pArrayGoodsValue, int *pArrayGoodsCount);
    void DisPlay(int maxValue);
    
    int main() 
    {
    	Init();
    
    	int maxValue = GetMaxValue(goods_total_num, package_total_contain, pArrayGoodsWeight, pArrayGoodsValue, pArrayGoodsCount);
    
    	//maxValue的值为-1时,表示用户的输入非法,程序直接结束
    	if (maxValue == -1)
    	{
    		system("pause");
    		return 0;
    	}
    
    	DisPlay(maxValue);
    
    	system("pause");
    
    	return 0;
    
    }
    
    /* 初始化函数,进行基本数据(背包的容量、物品的数量以及各个物品的重量与价值)的初始化 */
    void Init() 
    {
    	printf("请输入背包的的最大容量:");
    	scanf("%d", &package_total_contain);
    
    	printf("请输入物品的数量:");
    	scanf("%d", &goods_total_num);
    
    	//背包的重量有0的这一列,所以分配的空间要加1
    	pArrayGoodsWeight = (int *)malloc(sizeof (int) * (goods_total_num + 1));	
    	for (int i = 1; i <= goods_total_num; i++) 
    	{
    		printf("请输入第%d个物品的重量:",i);
    		scanf("%d", pArrayGoodsWeight + i);
    	}
    
    	printf("\n");
    	//物品的编号有0的这一行,所以分配的空间要加1
    	pArrayGoodsValue = (int *)malloc(sizeof (int) * (goods_total_num + 1));
    	for (int i = 1; i <= goods_total_num; i++) 
    	{
    		printf("请输入第%d个物品的价值:",i);
    		scanf("%d", pArrayGoodsValue + i);
    	}
    
    	//该数组与物品编号一一对应,选中就置为1,未选中就置为0,刚开始时全部初始化为0,也是从1开始存储的
    	pArrayGoodsCount = (int *)malloc(sizeof(int) * (goods_total_num + 1));
    	for (int i = 1; i <= goods_total_num; i++) 
    	{
    		pArrayGoodsCount[i] = 0;
    	}
    
    	/* 进行用户当前基本输入数据的显示,方便用户的对比 */
    	printf("\t\t\t\t您输入的数据如下图所示\n\n");
    
    	printf("\t\t   物品序号\t\t   物品重量\t\t   物品价值\n");
    
    	for (int i = 1; i <= goods_total_num; i++)
    	{	
    		printf("\t\t%8d\t\t%8d\t\t%8d\n", i, pArrayGoodsWeight[i], pArrayGoodsValue[i]);
    	}
    	printf("\n");
    }
    
    /*
    	该函数实现生成最大价值表以及得出实现的最大价值和物品选择序列
    	@param  goods_total_num			物品的总数量
    	@param  package_total_contain   背包的最大容量
    	@param  pArrayGoodsWeight		指向保存物品重量数组的首地址的指针变量
    	@param  pArrayGoodsValue	    指向保存物品价值数组的首地址的指针变量
    	@param  pArrayGoodsCount        指向保存物品是否被选中数组的首地址的指针变量
    **/
    int GetMaxValue(int goods_total_num, int package_total_contain, int *pArrayGoodsWeight, int *pArrayGoodsValue, int *pArrayGoodsCount) {
    
    	//表示用户输入了背包容量或物品数量非法时,直接返回-1,将不执行生成最大价值表的程序
    	if (goods_total_num <= 0 || package_total_contain <= 0)
    	{
    		return -1;
    	}
    
    	//表格的行数等于物品的数量,每个物品对应一行数据,由于有一行全为0,所以要加上1
    	int row_num = goods_total_num + 1;
    
    	//表格的列是按照背包重量从1开始进行递增,由于有背包重量是0的那一列,所以列数等于背包重量加1
    	int col_num = package_total_contain + 1;
    
    	//创建一个value指针变量,存放行的指针数组信息
    	int ** value = (int **)malloc(sizeof (int *));
    
    	//创建行数组,并将首地址发送给value指针
    	value = (int **)malloc(sizeof(int *) * row_num);
    
    	//创建列数组,并将首地址发送给行指针数组
    	for (int i = 0; i < col_num; i++) 
    	{
    		value[i] = (int *)malloc(sizeof(int) * col_num);
    	}
    
    	//进行初始化操作,初始化第0行,设置该行数值为0
    	for (int i = 0; i < col_num; i++)
    	{
    		value[0][i] = 0;
    	}
    
    	//进行初始化操作,初始化第0列,设置该行数值为0
    	for (int i = 0; i < row_num; i++) 
    	{
    		value[i][0] = 0;
    	}
    
    	//进行计算,算出每一行每一列的最大价值,i表示物品编号,j表示背包容量
    	for (int i = 1; i < row_num; i++) 
    	{
    		for (int j = 1; j < col_num; j++) 
    		{
    			//如果是该中情况,表明此时背包已经装不下了,该件物品将不会放入背包
    			value[i][j] = value[i - 1][j];
    
    			//如果物品能装入背包,此时的最大价值是该temp值
    			int tempValue = value[i - 1][j - pArrayGoodsWeight[i]] + pArrayGoodsValue[i];
    
    			//当物品能够放入背包中,并且放入的价值大于不放入的价值时,改变此时的最大价值
    			if (pArrayGoodsWeight[i] <= j && tempValue > value[i][j])
    			{
    				value[i][j] = tempValue;
    			}
    		}
    	}
    	
    	//最大价值表的列的下标最大值是col_num - 1
    	int j = col_num - 1;
    
    	/* 逆推法求出装入的物品,从最右下角开始往前推 */
    	for (int i = row_num - 1; i > 0; i--) 
    	{
    		//如果后面的价值大于前一个,表示该物品被选进了背包
    		if (value[i][j] > value[i - 1][j]) 
    		{
    			//设置该物品被选中,作为一种标记,设置其值为1,以便知道哪些被选中了
    			pArrayGoodsCount[i] = 1;
    
    			//将该物品的重量从总的重量中减去
    			j -= pArrayGoodsWeight[i];
    		}
    	}
    
    	//记录最大的价值
    	int max_value = value[row_num - 1][col_num - 1];
    
    	printf("\n");		//输出一个换行符
    
    	printf("\t最大价值表如下图所示\n");
    
    	printf("   ");		//输出3个空格使数据对齐
    
    	for (int i = 0; i < col_num; i++)
    	{
    		printf("%3d", i);	//进行列标题的输出,表示背包的重量
    	}
    
    	printf("\n");		//输出一个换行符
    
    	//进行当前每一个value[i][j]值的打印,行数等于物品数量加1,纵向数量等于背包最大容量加1
    	for (int i = 0; i <= goods_total_num; i++)
    	{
    		printf("%3d", i);	
    
    		for (int j = 0; j <= package_total_contain; j++)
    		{
    			printf("%3d", value[i][j]);
    		}
    
    		printf("\n");	//每输出一行进行一次换行操作
    	}
    
    	printf("\n");		//输出一个换行符
    
    
    	return max_value;
    }
    
    /* 该函数实现最终结果的显示 */
    void DisPlay(int maxValue) 
    {
    	printf("实现的最大价值是:%d\n", maxValue);
    
    	printf("选取的物品序列是:");
    
    	for (int i = 1; i <= goods_total_num; i++) 
    	{
    		if (pArrayGoodsCount[i] == 1)
    		{
    			printf("%d ", i);
    		}
    	}
    	printf("\n");	
    }
    

    运行的结果如下图所示

    在这里插入图片描述

    展开全文
  •  和分治一样,动态规划(dynamicprogramming)是通过组合子问题而解决整个问题的解。  分治是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解。动态规划适用于子问题不独立的情况,也...
    关键字:子问题不独立、子问题结果存储、空间换时间

    一、基本概念:
            和分治法一样,动态规划(dynamicprogramming)是通过组合子问题而解决整个问题的解。
            分治法是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解。动态规划适用于子问题不独立的情况,也就是各子问题包含公共的子问题。此时,分治法会做许多不必要的工作,即重复地求解公共的子问题。动态规划算法对每个子问题只求解一次,将其结果保存起来,从而避免每次遇到各个子问题时重新计算答案。

    二、算法基本思路:
          两种方法:
        1.自顶向下(又称记忆化搜索、备忘录):基本上对应着递归函数实现,从大范围开始计算,要注意不断保存中间结果,避免重复计算
        2.自底向上(递推):从小范围递推计算到大范围
          动态规划的重点:递归方程+边界条件

    三、算法特点:
        1. 动态规划任何一个i+1阶段都仅仅依赖i阶段做出的选择,而与i之前的选择无关。但是动态规划不仅求出了当前状态的最优值,而且同时求出了到中间状态的最优值;
        2. 缺点:空间需求大;

    四、适用问题
          适合适用动态规划的问题必须满足最优化原理、无后效性和重叠性。

          1.最优化原理(最优子结构性质)一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

          2.无后效性  将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。

          3.子问题的重叠性  动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。
     
    五、算法的实现框架
    for(j=1; j<=m; j=j+1) // 第一个阶段
       xn[j] = 初始值;
     
     for(i=n-1; i>=1; i=i-1)// 其他n-1个阶段
       for(j=1; j>=f(i); j=j+1)//f(i)与i有关的表达式
         xi[j]=j=max(或min){g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};
     
    t = g(x1[j1:j2]); // 由子问题的最优解求解整个问题的最优解的方案
     
    print(x1[j1]);
     
    for(i=2; i<=n-1; i=i+1)
    {  
         t = t-xi-1[ji];
     
         for(j=1; j>=f(i); j=j+1)
            if(t=xi[ji])
                 break;
    }
      
    六、实例分析

        动态规划算法可以求解很多问题,比如矩阵乘法、最长公共子序列、构造最优二叉查找树等,现就著名的最长公共子序列问题,采用动态规划法分析之。

        相关定义

          子序列:若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij.
          公共子序列:给定2个序列XY,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列XY公共子序列.
          最长公共子序列:给定2个序列X={x1,x2,,xm}Y={y1,y2,,yn},找出XY的最长公共子序列.
            如:序列ABCDEF和ADFGH的最长公共子序列为ADF

          注意:最长公共子串(Longest Common Substirng)和最长公共子序列(Longest Common Subsequence,简称LCS)的区别为是最长公共子串的串是一个连续的部分,而最长公共子序列则是从不改变序列的顺序,而从序列中去掉任意的元素而获得新的序列;通俗的说就是子串中字符的位置必须是连续的而子序列则可以不必连续。

       问题描述给定2个序列X={A,B,C,B,D,A,B}Y={B,D,C,A,B,A},找出XY的最长公共子序列.(转载1)(转载2)

       算法分析思路

         1.分析最优子结构性质:

              设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,则

           (1)若xm=yn,则zk=xm=yn,且z1,z2,…, zk-1是否为x1,x2,…,xm-1和y1,y2,…,yn-1的最长公共子序列.
           (2)若xm≠yn且zk≠xm,则Z是x1,x2,…,xm-1和Y的最长公共子序列.
           (3)若xm≠yn且zk≠yn,则Z是X和y1,y2,…,yn-1的最长公共子序列.

          由此可见,2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列.因此,最长公共子序列问题具有最优子结构性质.当问题具有最优子结构性质和子问题重叠性质时就可以用动态规划算法解决该问题.

         2.由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系.用c[i][j]记录序列和的最长公共子序列的长度.其中,Xi={x1,x2,…,xi},Yj={y1,y2,…,yj}.当i=0或j=0时,空序列是Xi和Yj的最长公共子序列.故此时C[i][j]=0.其它情况下,由最优子结构性质可建立递归关系如下:

       

          回溯输出最长公共子序列过程:

           flow


       算法分析由于每次调用至少向上或向左(或向上向左同时)移动一步,故最多调用(m + n)次就会遇到i = 0或j = 0的情况,此时开始返回。返回时与递归调用时方向相反,步数相同,故算法时间复杂度为Θ(m + n)

       算法实现

    //LCS  最长公共子序列
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX 100
    
    void LCS(char *x, char *y,int x_len, int y_len, int common_len[][MAX], int b[][MAX])
    {
        //common_len[i][j]存储的是x的第i位与有的第j位的公共子序列的长度
        //b[i][j] 记录获得common_len[i][j]的路径:分别为0 -1 1,便于回溯输出公共子串
    
        int i,j;
        
        for (i = 0; i < x_len; i++)
            common_len[i][0] = 0;
        for (j = 0; j < y_len; j++)
            common_len[0][j] =0;
    
        for (i = 1; i <= x_len; i++)
        {
            for (j = 1; j <= y_len; j++)
            {
                if (x[i-1] == y[j-1])  //从零开始存储,所以第i位为x[i-1]
                {
                    common_len[i][j] = common_len[i-1][j-1] + 1;
                    b[i][j] = 0;
                }
                else if (common_len[i-1][j] >= common_len[i][j-1])
                {
                    common_len[i][j] = common_len[i-1][j];
                    b[i][j] = -1;
                }
                else
                {
                    common_len[i][j] = common_len[i][j-1];
                    b[i][j] = 1;
                }
            }
        }
    }
    
    void backtrack(int i, int j,int b[][MAX], char *x)
    {
        if (0 == i || 0 == j) 
            return;
        else if (0 == b[i][j])
        {
            backtrack(i-1,j-1,b,x);
            printf("%c",x[i-1]);
        }
        else if(-1 == b[i][j])
        {
            backtrack(i-1,j,b,x);
        }
        else
        {
            backtrack(i,j-1,b,x);
        }
    }
    
    int main()
    {
        int x_len,y_len;
        char x[MAX] = "ABCBDAB";
        char y[MAX] = "BDCABA";
        int common_len[MAX][MAX];
        int b[MAX][MAX];
    
        x_len = strlen(x);
        y_len = strlen(y);
    
        LCS(x,y,x_len,y_len,common_len,b);
        backtrack(x_len,y_len,b,x);
        
        printf("\n");
        
        
        return 0;
    }
    


    转载请注明出处:http://blog.csdn.net/daijin888888/article/details/53115323
    展开全文
  • 动态规划法与分治方法   动态规划(Dynamic Programming)与分治方法相似,都是通过组合子问题的解来求解原问题。不同的是,分治方法通常将问题划分为互不相交的子问题,递归地求解子问题,再讲它们的解组合起来...

    动态规划法与分治方法

      动态规划(Dynamic Programming)与分治方法相似,都是通过组合子问题的解来求解原问题。不同的是,分治方法通常将问题划分为互不相交子问题递归地求解子问题,再讲它们的解组合起来,求出原问题的解。而动态规划应用于子问题重叠的情况,即不用的子问题具有公共的子子问题。在这种情况下,如果采用分治算法,则分治算法会做许多不必要的工作,它会反复地求解那些公共子子问题。对于动态规划法,它对每个子子问题只求解一次,将其保存在一个表格中,从而无需每次求解一个子子问题时都重新计算,避免了这种不必要的计算工作。
      也就是说,动态规划法与分治方法相比,是用空间来换时间,而时间上获得的效益是很客观的,这是一种典型的时空平衡(time-memory trade-off)的策略。通常,动态规划法用来求解最优化问题(optimization problem),如斐波那契数列求值问题,钢条切割问题,0-1背包问题,矩阵链乘法问题,最长公共子序列(LCS)问题,最优二叉搜索树问题等。
      一般情况下,动态规划算法的步骤如下:

    1. 刻画一个最优解的结构特征。
    2. 递归地定义最优解的值。
    3. 计算最优解的值,通常采用自底向上的方法。
    4. 利用计算出的信息构造一个最优解。

      接下来,我们将从斐波那契数列求值这个简单的例子入手,来分析动态规划法的具体步骤和优点。

    斐波那契数列

      斐波那契数列记为{f(n)},其表达式如下:

    {f(0)=0f(1)=1f(n)=f(n1)+f(n2),n2

      具体写出前几项,就是:0,1,1,2,3,5,8,13,21,34,55,89,144,233……
      接下来,我们将会采用递归法和动态规划法来求解该数列的第n项,即f(n)的值。

    递归法求解

      首先,我们采用递归法来求解斐波那契数列的第n项f(n),其算法描述如下:

    function fib(n)
        if n = 0 return 0
        if n = 1 return 1
        return fib(n − 1) + fib(n − 2)

    分析上述伪代码,先是定义一个函数fib(n),用来计算斐波那契数列的第n项,当n2时,它的返回值会调用函数fib(n-1)和fib(n-2).当n=5时,计算fib(5)的函数调用情况如下图所示:




    在计算fib(5)时,fib(5)调用1次,fib(4)调用1次,fib(3)调用2次,fib(2)调用3次,fib(1)调用5次,fib(0)调用3次,一共调用函数fib()15次。由此,我们可以看到,在计算fib(5)时,存在多次重复的fib()函数的调用,当n增大时,重复调用的次数会急剧增加,如计算fib(50)时,fib(1)和fib(0)大约会被调用2.4×1010次。由此可见,该算法的效率并不是很高,因为该算法的运行时间是指数时间。
      我们用Python实现上述算法,并计算f(38)的值及运算时间。Python代码如下:

    import time
    
    # recursive method
    def rec_fib(n):
        if n <= 1:
            return n
        else:
             return rec_fib(n-1) + rec_fib(n-2)
    
    # time cost of cursive method
    t1 = time.time()
    t = rec_fib(38)
    t2 = time.time()
    
    print('结果:%s, 运行时间:%s'%(t, t2-t1))

    输出结果如下:

    结果:39088169, 运行时间:22.93831205368042

    动态规划法求解

      在使用递归法来求解斐波那契数列的第n项时,我们看到了递归法的不足之处,因为递归法在使用过程中存在大量重复的函数调用,因此,效率很差,运行时间为指数时间。为了解决递归法存在的问题,我们可以尝试动态规划法,因为动态规划法会在运行过程中,保存上一个子问题的解,从而避免了重复求解子问题。对于求解斐波那契数列的第n项,我们在使用动态规划法时,需要保存f(n-1)和f(n-2)的值,牺牲一点内存,但是可以显著地提升运行效率。
      动态规划法来求解斐波那契数列第n项的伪代码如下:

    function fib(n)
    
        var previousFib := 0, currentFib := 1
    
        if n = 0
        return 0
        else if n = 1
        return 1
    
        repeat n−1 times
            var newFib := previousFib + currentFib
            previousFib := currentFib
            currentFib := newFib
    
        return currentFib

    在上述伪代码中,并没有存在重复求解问题,只是在每次运行过程中,保存上两项的值,再利用公式f(n)=f(n1)+f(n2)来求解第n项的值。用Python实现上述过程,代码如下:

    import time
    
    # bottom up approach of Dynamic Programming
    def dp_fib(n):
        previousFib = 0
        currentFib = 1
        if n <= 1:
            return n
    
        # repeat n-1 times
        for _ in range(n-1):
            newFib = previousFib + currentFib
            previousFib = currentFib
            currentFib = newFib
    
        return currentFib
    
    # time cost of DP method
    t1 = time.time()
    t = dp_fib(38)
    t2 = time.time()
    
    print('结果:%s, 运行时间:%s'%(t, t2-t1))

    输出结果如下:

    结果:39088169, 运行时间:0.0

      显然,使用动态规划法来求解斐波那契数列第n项的运行效率是很高的,因为,该算法的时间复杂度为多项式时间。

    参考文献

    1. 算法导论(第四版)
    2. https://www.cs.upc.edu/~jordicf/Teaching/programming/pdf/IP07_Recursion.pdf
    3. https://www.saylor.org/site/wp-content/uploads/2011/06/Dynamic-Programming.pdf

    附录

    用递归法和动态规划法来求解该数列的第n项,完整的Python代码如下:

    # calculate nth item of Fibonacci Sequence
    import time
    
    # recursive method
    def rec_fib(n):
        if n <= 1:
            return n
        else:
             return rec_fib(n-1) + rec_fib(n-2)
    
    # bottom up approach of Dynamic Programming
    def dp_fib(n):
        previousFib = 0
        currentFib = 1
        if n <= 1:
            return n
    
        # repeat n-1 times
        for _ in range(n-1):
            newFib = previousFib + currentFib
            previousFib = currentFib
            currentFib = newFib
    
        return currentFib
    
     # time cost of cursive method
    t1 = time.time()
    t = rec_fib(38)
    t2 = time.time()
    print('结果:%s, 运行时间:%s'%(t, t2-t1))
    # time cose of DP method
    s = dp_fib(38)
    t3 = time.time()
    print('结果:%s, 运行时间:%s'%(t, t3-t2))

    输出结果如下:

    结果:39088169, 运行时间:22.42628264427185
    结果:39088169, 运行时间:0.0

    完整的Java代码如下:

    package DP_example;
    
    import java.util.Date;
    import java.math.BigInteger;
    
    public class fib {
        // 主函数
        public static void main(String[] args) {
            Date start_time =  new Date(); //开始时间
            int n = 38;
            BigInteger t1 = DP_fib(n);  // 动态规划法求解
            Date end_time1 =  new Date(); // 结束时间
            Long cost_time1 = end_time1.getTime()-start_time.getTime();  // 计算时间,返回毫秒数
            System.out.println(String.format("The fib(%d) is %s.\nCost time is %.3fs.", n, t1, cost_time1*1.0/1000));
    
    
            BigInteger t2 = rec_fib(n);  // 递归法求解
            Date end_time2 =  new Date(); // 结束时间
            Long cost_time2 = end_time2.getTime()-end_time1.getTime();  // 计算时间,返回毫秒数
            System.out.println(String.format("The fib(%d) is %s.\nCost time is %.3fs.", n, t2, cost_time2*1.0/1000));
    
        }
    
        // 利用递归方法计算斐波那契数列的第n项
        public static BigInteger rec_fib(int n){
            if(n == 0)
                return BigInteger.ZERO;
            if(n ==1)
                return BigInteger.ONE;
            else
                return rec_fib(n-1).add(rec_fib(n-2));
        }
    
        // 利用动态规划法(DP)计算斐波那契数列的第n项
        public static BigInteger DP_fib(int n){
            if(n == 0)
                return BigInteger.ZERO;
            if(n == 1)
                return BigInteger.ONE;
            else {
                BigInteger previousFib = BigInteger.ZERO;
                BigInteger currentFib = BigInteger.ONE;
                BigInteger newFib;
    
                for(int i=1; i<n; i++){ // 重复循环n-1次
                    newFib =  previousFib.add(currentFib);
                    previousFib = currentFib;
                    currentFib = newFib;
                }
    
                return currentFib;
            }
        }
    }

    输出结果如下所示:

    The fib(38) is 39088169.
    Cost time is 0.001s.
    The fib(38) is 39088169.
    Cost time is 2.172s.
    展开全文
  • 一、熟知动态规划有以下的优点优点1.减少了计算量,随着段数的增加,计算量大大减少。 优点2.计算中得到了很多有用的中间过程,不仅得到了出发点到终点的最短路径,而且得到了中间各点到终点的最短路径。 二、...

    讨论动态规划的优点 - 相比于穷举法 - (以最短路径为例)

    一、熟知动态规划有以下的优点:

    优点1.减少了计算量,随着段数的增加,计算量大大减少。

    优点2.计算中得到了很多有用的中间过程,不仅得到了出发点到终点的最短路径,而且得到了中间各点到终点的最短路径。

    二、回顾动态规划的基本思想:


    三、通过以下例子,我们将清楚的看到动态规划的优点:(以最短路径为例)

    1、段数较少

    以下的图为例


    说明动态规划的优点,这里我们以整个过程中做的加法次数为指标,次数越少,我们认为计算量越好,效率越高。

    穷举法的加法次数:1*2*3*1 = 6

    动态规划(逆向D->A):2*3+1*2 = 8

    (说明:动态规划第一步从B->D,不从C->D,C->D不存在选择最短路)

    这个似乎不能说明动态规划比穷举法的计算量小,其实是阶段数较少,当阶段数增加后,动态规划的优势明显体现。

    2、段数较多


    (假设每一层的某个状态都可以到达下一层的每个状态)

    穷举法的加法次数:1*2*3*4*4*3*2*1 = 576

    动态规划(逆向D->A):3*2+4*3+4*4+3*4+2*3+1*2 = 54

    这下明显可以看出动态的优势,大大减少了计算量;至于说得到有用的中间量,这个不用多解释。

    3、量化直接说明动态规划减少计算量的优势

    以二中的特殊情况为例,两边对称,段数为偶数的情况,所以一共有2n个阶段(加上始末)。

    穷举法的加法次数:(1*2*3*…*n)^2 = (1*2*3*…*n)*(1*2*3*…*n

    动态规划的加法次数:(n*n+(n-1)n+(n-2)(n-1)+...+1*2)*2-1*2(n*n+(n-1)n+(n-2)(n-1)+...+1*2)*2 < (n*n+(n-1)n+(n-2)n+...+1*n)*2 = (n+(n-1)+(n-2)+...+1)*n*2

    当n>3时,(1*2*3*…*n)> (n+(n-1)+(n-2)+...+1) 这个成立,随着n变大差距越越大,毕竟是相乘嘛!

    (1*2*3*…*n)> n*2

    所以很明显,当段数增加时,动态规划的计算量是成倍成倍的减少。

    四、注意动态规划中的无后效性(马尔可夫性)

    如果某阶段状态给定后,则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响;
    过程的过去历史只能通过当前的状态去影响它未来的发展;构造动态规划模型时,要充分注意是否满足无后效性的要求;

    展开全文
  • 一篇关于动态规划的背包问题.主要讲解了如何利用动态规划思想来解决问题.
  • } (3)测试数据和运行结果 三、分析和经验: 关于0/1背包问题,每个背包分别有自己的重量和价值,需要根据背包的容量来确定最解,动态规划法的思想可以很好解决这个问题,在对问题求解时,.减少了计算量,随着段数...
  • 动态规划法解决0/1背包问题详解

    万次阅读 多人点赞 2016-10-19 16:06:24
    动态规划(dynamic programming)是求解决策过程最优化的数学方法,把多阶段过程转换为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法。 基本思想 将待求解的问题分解成...
  • (一)分治(divide and conquer method) 是将待求解的原问题划分成k个较小规模的子问题,对这k个子问题分别求解。如果子问题的规模仍然不够小,则再将每个子问题划分为k个规模更小的子问题,如此分解下去,直到...
  •    可以看到以上四种算法,每种都有各自的优缺点。对于暴力求解方法,想法最简单,但是算法效率不高。Kanade算法简单高效,但是不易想到。分治算法运行效率高,但其分支过程的设计较为麻烦。动态规划法想法巧妙,...
  • 0-1背包问题的动态规划法与回溯法

    千次阅读 2018-11-22 22:30:08
    一、动态规划 状态转移方程: 从前往后: if(j&gt;=w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]); else m[i][j]=m[i-1][j]; 从后往前: if(j&gt;=w[i]) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+...
  • 首先,这些方法所要解决的问题,一般都是决策问题。而贪心一般是来求解最优问题的,而且他们其实都是在对问题的状态空间树进行搜索,在这个状态空间树中搜索最佳的路径以便求出最优策略。...这也造成了它的一个缺点
  • 动态规划模型相对于静态规划模型的优点: 1. 能够得到全局最解; 2. 可以得到一族最解; 3. 由于动态规划方法反映了动态过程演变的联系和特征,在计算时可以利用实际知识和经验提高求解效率。动态规划模型的缺点...
  • 动态规划是将原问题分解为多个子问题,通过计算出子问题的结果构造一个最解。动态规划通过迭代自底向上求解,动态规划将分解后的子问题理解为相互间有联系,有重叠的部分; 算法的应用:装配线,矩阵乘法,最长...
  • 一般实际生活中我们遇到的算法分为四类:  一> 判定性问题  二> 最优化问题  三> 构造性问题  四> 计算性问题 而今天所要总结的算法就是着重解决最优化问题 《算法之道》对三种算法...动态规划
  • 当所给的整数均为负数时定义子段和为0,依此定义,所求的最值为: Max{0,a[i]+a[i+1]+…+a[j]},1&amp;amp;amp;lt;=i&amp;amp;amp;lt;=j&amp;amp;amp;lt;=n 例如,当(a[1],a[2],a[3],a[4],a[5],a[6])=...
  • 动态规划快速入门

    千次阅读 2019-05-19 16:07:56
    动态规划算法一直是面试手撕算法中比较有挑战的一种类型。很多的分配问题或者调度问题实际上都可能用动态规划进行解决。(当然,如果问题的规模较大,有时候会抽象模型使用动归来解决,有时候则可以通过不断迭代的...
  • 动态规划

    千次阅读 2013-12-26 20:06:01
    动态规划初步 林厚从 引例:城市交通 有n个城市,编号1~n,有些城市之间有路相连,有些则没有,有路则当然有一个距离。现在规定只能从编号小的城市到编号大的城市,问你从编号为1的城市到编号为n的城市之间...
  • 动态规划的突出优点是代码的简介性和运算的快速性。今天在刷到lc上的115题 不同的子序列时,这道题只有用动态规划才能解出来。leetcode上的题目大多有时间限制,在这种情况下动态规划就显得尤为重要。动态规划常用于...
  • 分治法所能解决的问题一般具有的几个特征: (1)该问题的规模缩小到一定的程度就可以容易地解决 ...动态规划法所能解决的问题一般具有的几个特征: (1)该问题可以分解为若干规模较小的相同问题,即该问...
  • 动态规划常见类型总结

    千次阅读 多人点赞 2019-03-26 23:55:28
    严格来说,递推不属于动态规划问题,因为动态规划不仅有递推过程,还要有决策(即取最优),但广义的动态规划是可以包含递推的,递推是一类简单的、特殊的动态规划,毕竟动态规划与递推密不可分。动态规划类型主要...
  • 递归和动态规划的区别

    千次阅读 2020-06-04 19:05:13
    递归:自上至下,把大问题分解成小问题解决。 动态规划:自下至上,通过解决小问题,集合为解决大问题。...动态规划缺点:会记录每一个问题的结果,内存消耗较大。 优点:不会计算相同问题,时间消耗较小。 ...
  • 动态规划算法

    2017-03-16 00:52:19
    1 动态规划的思想 动态规划也是采取的分治的思想,关键点就在于怎么去分。 在钢管分割的问题上,可以这样去思考问题,假设钢管长度为N,最解是将其分割为k段。那么当将钢管分割为2段时, 我们假设x = L(1) + L(2) ...
  • 0-1背包问题是个很经典的问题,规模较小时常用回溯来类似于枚举的方法进行所有的选择方案的求解,但是由下图显而易见,这个过程中进行了很多次重复性的计算,故完全可以用动态规划的方式,利用状态转移表提前计算...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,777
精华内容 10,310
关键字:

动态规划法的优缺点