精华内容
下载资源
问答
  • 五大算法思想 动态规划 矩阵连乘问题、走金字塔问题、最长公共子序列问题、最长递增子序列问题、0-1背包问题、完全背包问题

    一、理论基础

      动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推的方式去解决。动态规划算法的基本思想与分治法类似,也是将待求解的问题分解为若干个子阶段,按顺序求解子阶段。与分治不同的是,在动态规划过程中,前一子问题的解,为后一子问题的求解提供了有用的信息,也就是说前后阶段的问题求解存在依赖关系。在求解任一子问题时,通过决策保留那些有可能达到最优的局部解。依次解决各子问题,最后一个子问题就是初始问题的解。
      以上都是官方说法,在实际运用动态规划时,每个人都有不同的理解。此处以爬楼梯问题为例,来介绍一下一种解决动态规划问题的思路。爬楼梯问题的描述:

      一个人爬楼梯,一次只能爬一阶或两阶,当总共有n阶楼梯时,有多少种爬法。

      本文中解决动态规划问题的思路是,确定动态规划四要素:

    • 1、问题的阶段
        在该问题中,在楼梯的每层台阶上,都有着不同数量的往上爬完楼梯的可能性,也就是说每层台阶其实就意味着不同的阶段。找阶段的过程,其实就是拆分问题的过程。假如楼梯总共有10层,每次只能向上爬1层或2层楼梯。那么解决这个问题的最后一个阶段就是可以理解为从第10层楼梯往上爬(因为每次只能爬1或2层,所以这个阶段只能爬到8层或9层),再细说的话,也就是:从10层爬到9层或8层是解决该问题的第一阶段。
        也许有人会问,为什么要这样划分阶段?首先,在动态规划中,大问题不能像分治那样,拆分成完全相同的子问题,各子阶段是有依赖关系的,所以需要确定一个解决问题的“起点”和“终点”。而在动态规划中,“从底向上”的方案常常使用,所以此处就是从最底部(10)开始,作为解决问题的“起点”。
    • 2、每个阶段的状态
        在第一步中,已经对问题划分了阶段,在划分阶段后,要解决问题,还需要做的是定义阶段的状态。在该问题中,我们确定解决问题的第一个阶段是:在第10层楼梯时。在动态规划问题中,和子问题相关的各个变量的一组取值,称之为一个"状态",一个状态对应一个或多个子问题所谓的在某个状态的值,这个就是状态所对应的子问题的解,所有状态的集合称为"状态空间"。这个状态的解释比较官方,其实每个阶段的状态可以简单理解为:要用动态规划思想解决问题,需要在某个阶段定义的变量值,这个变量可以是一个变量值,也可以是一组变量值。
        在动态规划中,实际运用到的常常是一维数组dp[ ]或二维数组dp[ ][ ]。在爬楼梯问题中,我们就可以定义dp[10],该变量的含义是在第10层台阶时,往上爬总共有多少种可能性。
    • 3、找数组的边界值
        边界值常常是动态规划方案“终点”的计算值,往往在“终点”或邻近“终点”时,才能直接计算一些变量的变化值。比如在爬楼梯问题中,从第10层楼梯,有多少种可能性,一下子是计算不出来的。但是当处在第1层或第2层楼梯时,就可以直接计算出往上爬楼梯的可能性,这就是在爬楼梯问题中的“边界值”。
    • 4、从前一个阶段转化到后一个阶段之间的递推关系
        前面的三个步骤都可以说是铺垫,动态规划中最核心的就是这最后一步:找状态转移方程,其实也就是每个阶段的变量怎样变化的关系式(这一步在每个问题中,都可能有不同的关系式,需要视具体情况而定)。在爬楼梯问题中,我们定义的在第10层往上爬的变量为dp[10],此时题中有个条件是:一次只能爬一阶或两阶,这个条件就决定了转移方程的写法。
        因为每次只能只能爬1或2个台阶,所以,从第10层楼梯只能爬到第9层或第8层,并且在从第10层爬到第9层和从第10层爬到第8层,是不存在交叉关系的过程。处在第9层和第8层时的变量,很容易想到是dp[9]和dp[8],所以在该问题中,从第10层往上爬的状态转移方程就是:dp[10]=dp[9]+dp[8]。在推广到后续阶段过程中,状态转移方程就是:dp[n]=dp[n-1]+dp[n-2]。

    1.1 适用场景

      能用动态规划解决的问题具有的特征:
       1>最优化原理
        如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。这个特征较容易理解,常见就是在某个问题汇总存在最值。
       2>无后效性
        即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。这个特征可以理解为:可以存储不同阶段的变量值。这样的话,在后续阶段中,就不用重复求一些之前阶段的值。
       3>有重叠子问题
        即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势。该特征是说,解问题的不同阶段中,子问题是有重叠、依赖关系的。如果子问题不存在重叠、依赖关系,使用分治往往更好。

    1.2 使用步骤

      在动态规划的步骤上,每个人也有每个人的理解。一种比较容易的步骤是:
       1>划分阶段
        按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。
       2>确定状态
        将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
       3>确定决策并写出状态转移方程
        因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
       4>寻找边界条件
        给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。

    1.3 常用方法-填表法

      在使用动态规划思想解决问题时,最常用的方法是填表法,该方法是以未知的量为基础,通过已知的量来刷新当前的未知量。此处借用一张网上的图来表示:
              
      由上图可知,填表法的计算过程就是:借用初始变量和状态转移方程将动态规划表逐渐填完,再找出最值。

    1.4 经典例子

      常见例子如下:
       1>矩阵连乘
       2>走金字塔
       3>最长公共子序列
       4>最长递增子序列
       5>背包问题
      接下来将对这些例子进行实现,来探究动态规划的具体使用方法。

    二、常见例子

    2.1 矩阵连乘

       矩阵连乘也是常见的动态规划例子之一。该问题的形式如下:给出N个矩阵,矩阵是有序的,即相邻矩阵之间可以进行乘法运算,求这些矩阵最小的相乘次数。
       矩阵乘法是满足结合律的,所以在矩阵连乘的过程中,可以有多种相乘顺序,这种相乘次序,可以用加括号来确定。如存在着下面三个维度的矩阵:A1(30 * 15)、A2(15 * 5)、A3(5 * 10),这三个矩阵连乘时,有两种计算次序:(A1A2)A3和A1(A2A3)。
      以矩阵(3 * 2)和B(2 * 4)为例,两个矩阵的相乘的计算量如下:
          
      回到矩阵A1、A2、A3的矩阵连乘问题。当进行(A1A2)A3运算时,乘法计算次数为30 * 15 * 5+30 * 5 * 10=3750,;进行A1(A2A3)运算时,乘法计算次数为15 * 5 * 10+30 * 15 * 10=5250。由此可见,不同的运算顺序,会影响到乘法的计算次数。
      对于矩阵连乘AiAi+1Ai+2……Aj的最优解问题,假设在第k位置上找到最优解,则完整的矩阵连乘问题就变成了两个子矩阵连乘问题,即(AiAi+1……Ak)和(Ak+1……Aj)。
      此时用m[i][j]表示矩阵连乘的最优值,那么两个子矩阵连乘问题对应的最优值变成m[i][k],m[k+1][j]。阵连乘最优值递归式如下:
            
      此式子中的Pi-1 * Pk * Pj 代表的意思是划分后的两个矩阵的相乘后的乘法次数。
      矩阵相乘示例代码如下:

    public class MatrixMultiplication {
    	public static void main(String[] args) { 
    		int arr[ ] = {30,15,5,10};
    		int minMultiNum = getMinMultiNum(arr);
    		System.out.println("矩阵连乘时,乘法运行的最小次数是:"+minMultiNum);	
    	}
    	
    	private static int getMinMultiNum(int[] arr){
    		int minMultiNum = 0;
    		int length = arr.length;
    		/*存储断开位置结果*/
    		int[ ][ ] s = new int [length][length];
    		/*存储乘法计算结果*/
    		int[ ][ ] m = new int [length][length]; 
    		for(int i=0;i<length;i++){
    			for(int j=0;j<length;j++){
    				s[i][j] = 0;
    				m[i][j] = 0;
    			}
    		} 
    
    		/*r为子问题规模*/
    		for(int r=2; r<=length-1; r++){
    			for(int i=1; i<=length-1-r+1; i++){
    				int j = i+r-1;
    				/*将链ij划分为A(i)*(A[i+1:j])*/
    				m[i][j] = m[i+1][j] + arr[i-1]*arr[i]*arr[j];
    				/*s[ ][ ]存储各子问题的决策*/
    				s[i][j] = i; 
    				/*将链ij划分为(A[i:k])*(A[k+1:j])*/ 
    				for(int k=i+1; k<j; k++){
    					int tmp = m[i][k] + m[k+1][j] + arr[i-1]*arr[k]*arr[j];
    					if(tmp<m[i][j]){ 
    						m[i][j] = tmp;
    						s[i][j] = k;
    					}
    				}
    			}
    		}
    		
    		minMultiNum = m[1][length-1];
    		return minMultiNum;
    	}
    }
    

      测试结果如下:

    矩阵连乘时,乘法运行的最小次数是:3750

    2.2 走金字塔

      走金字塔问题也是常见的动态规划问题,该问题的形式是:有一个数字金字塔,例如:
          
      查找从最高点到底部任意处结束的路径(每一步可以从当前点走到左下方的点也可以到达右下方的点),使路径经过数字的和最大。
      在解该问题时,需要将数字金字塔稍微变形一下,变成下面形式:

    		int[ ][ ] arr = {
    				{13},
    				{11,8},
    				{12,7,26},
    				{6,14,15,8},
    				{12,7,13,24,11}
    		};
    

      在按步骤解决该问题前,我们先看看这问题该怎么解。既然要求最大路径,就是求一些数的相加之和最大,同时动态规划一般是自底向上的,所以要做的第一步就是让第4层和第5层相邻的数相加,然后将相加的结果的值存储在第四层(并且此时存储的的结果与第4层原有的数的量是相同的);再加这些相加的结果与第3层的数值再相加,存储相加结果到第3层,直到相加到了第1层,也就是最终的结果。
      接下来,按上面第一章节介绍的步骤来解该问题:
       1>划分阶段
        示例中的数字金字塔有5层,那么应该划分5个阶段,还是几个阶段呢?答案是4个,因为如果划分成5个阶段的话,就是每层金字塔都代表一个阶段。这样的话,在第5层金字塔的话,最大值肯定就是24,即当层数字最大值,但这个第5层的最大值,在更新下一阶段最大值时,不具备任何意义,因为从第4层开始,求的是两个数字之和的最大值。所以,该问题需要划分为4个阶段,对应到数字金字塔上是从第1层到第4层。
       2>确定状态
        在该问题中,每层保存一个临时最大值即可,用arr[ i ][ j ]表示。
       3>写状态转移方程
        此时,就要运用到该题中的规则了:每一步可以从当前点走到左下方的点也可以到达右下方的点。翻译成容易理解的话就是,arr[i][j]只可能和两个值相加:arr[i+1][j]、arr[i+1][j+1]。然后比较这两种相加结果,求出较大值就行,然后也就能推导出状态转移方程了:arr[ i ][ j ] += Math.max(arr[ i+1 ][ j ], arr[ i+1 ][ j+1 ])。
       4>寻找边界条件
        在第1步中,其实已经明确了部分边界条件“起点”,也就是从倒数第二层开始,终点也不难推导,就是第一层。
      有了上面的4步,就可以写代码了,示例代码如下:

    public class Pyramid {
    	public static void main(String[] args) { 
    		int[ ][ ] arr = {
    				{13},
    				{11,8},
    				{12,7,26},
    				{6,14,15,8},
    				{12,7,13,24,11}
    		};
    
    		int result = getMaxNum(arr);
    		System.out.println("用迭代法求得最大数字为:"+result);
    	}
    	
    	private static int getMaxNum(int[][] arr){
    		for(int i = arr.length-2; i>=0; i--){
    			for(int j = 0; j <= i; j++){
    				arr[ i ][ j ] += Math.max(arr[ i+1 ][ j ], arr[ i+1 ][ j+1 ]);
    			}
    		}
    		return arr[0][0];
    	}
    }
    

      测试结果如下:

    用迭代法求得最大数字为:86

      如果要打印出每阶段的结果,可以修改getMaxNum,修改后的代码如下:

    	private static int getMaxNum(int[][] arr){
    		for(int i = arr.length-2; i>=0; i--){
    			int temp = 0;
    			for(int j = 0; j <= i; j++){
    				arr[ i ][ j ] += Math.max(arr[ i+1 ][ j ], arr[ i+1 ][ j+1 ]);
    				temp = Math.max(arr[ i+1 ][ j ], arr[ i+1 ][ j+1 ]);
    			}
    			System.out.println(temp+" ");
    		}
    		return arr[0][0];
    	}
    

      此时测试结果为:

    24
    39
    65
    73
    用迭代法求得最大数字为:86

    2.3 最长公共子序列

       最长公共子序列也是常见的动态规划问题,该问题的形式是:两个字符串的公共子序列长度是多少?看个例子:字符串str1为"abcd",字符串str2为"aecd",则他们的最长公共子序列是"acd",最长公共子序列长度是3。由该例子可以看出,最长公共子序列并不一定要求是相连的,只要保证前后顺序一致即可。
      在按步骤解决该问题前,我们先看看这问题该怎么解。因为要遍历两个序列进行元素比较,所以常规的做法会有两个循环。我们假设把第一个字符串str1作为外层循环的序列,则首选要取出str1中的第一个字符’a’,然后逐个与str2中的字符比较,并且存储下与str2中每个元素比较的结果。如果相同,则记录为1,代表如果公共子序列以此字符开头的话,其长度为1(实质上是在原来的基础上+1,因为原来假设的默认值都是0)。然后将元素逐个比较完毕。两个序列最后一个元素的比较结果也就是最终的结果。
       解决该问题也是用填表法,创建一个二维数组dp[ ][ ]即可。接下来按上面第一章节介绍的步骤来解该问题:
       1>划分阶段
        在使用填表法解决问题的时候,表的维度是要参与动态规划的两个元素的长度+1。也就是说dp的宽高分别是str1.length()+1、str2.length()+1。为什么要这样设置动态表的维度?因为这样默认给第0行和第0列元素赋予元素0,也就是填表时的初始变量为0,方便接下来的填表过程,比如该问题的动态表如下:
            
        说了这么多动态表,和阶段有什么关系呢?个人理解,其实在动态表中,一行就是一个阶段。一行,在代码中体现为一个外层循环,在该问题中体现为一个字符的比较,当字符串中较前面的字符比较完成后,才能进入后面字符的比较过程,所以,一个字符的比较过程就是一个阶段。
       2>确定状态
        在使用填表法解决问题时,状态一般就用dp数组的元素表示,该问题中自然也用dp[i][j]表示。此处的dp[i][j]指的是当从字符串str1中拿出第i个元素,从字符串str2中拿出第j个元素比较,此时的公共子序列的长度。
       3>写状态转移方程
        写状态转移方程,是最核心的模块。先抛开填表法,直接看这个题,从两个字符串的第一个元素开始比较,如果两个字符相等,则此时的公共子序列为相等的元素,其长度为1;然后继续在比较下一个元素,如果两个字符串不相等,此时的公共子序列长度就延续了上个阶段的公共子序列长度,还是1。
        这两个过程,用代码表示的话,其实就是状态转移方程的全部,字符相等的情况下,公共字符串长度在现有情况下+1即可,用代码表示:

    dp[i][j] = dp[i - 1][j - 1] + 1;
    

        字符不相等的情况下,保持现有公共字符串长度即可,用代码表示:

    dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
    

       4>寻找边界条件
        在使用填表法解决动态规划问题时,当把表填完,就代表解决问题的过程已经结束,也就是所谓的边界条件。
      有了上面的4步,就可以写代码了,示例代码如下:

    public class MaxSequence {
    
        public static void main(String[] args) {
             String str1 = "abcd";
             String str2 = "adcd";
             int result = findMaxSequence(str1, str1.length(), str2, str2.length());
             System.out.println("公共子序列长度是:"+result);
        }
     
        public static int findMaxSequence(String str1, int str1length, String str2, int str2length) {
            int[][] dp = new int[str1length + 1][str2length + 1];
            for (int i = 0; i <= str1length; i++) {
                for (int j = 0; j <= str2length; j++) {
                    dp[i][j] = 0;
                }
            }
            for (int i = 1; i <= str1length; i++) {
                for (int j = 1; j <= str2length; j++) {
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
                    }
                }
            }
            
            System.out.println("动态规划表为:");
            for (int i = 0; i < str1.length()+1; i++) {
                for (int j = 0; j < str2.length()+1; j++) {
                    System.out.print(dp[i][j]+"\t");
                }
                System.out.println();
            }
            
            return dp[str1length][str2length];
        }
    }
    

      测试结果:

    动态规划表为:
    0 0 0 0 0
    0 1 1 1 1
    0 1 1 1 1
    0 1 1 2 2
    0 1 2 2 3
    公共子序列长度是:3

    2.4 最长递增子序列

      最长递增子序列也是常见的动态规划问题,该问题的形式是:一个序列中最长递增的子序列长度是多少?比如序列1、4、3、2、5,则最长的递增的子序列为1、2、5或1、3、5或1、4、5,其长度为3。该问题中,结果子序列也并不要求是相连的。其实,子序列问题都并不要求是连续的元素。
      在按步骤解决问题之前,我们先看看这个问题怎么解。我们首先要维护一张表,在这个表中存放的数据是:以原来序列中元素为结尾时,最长递增子序列的长度。举个例子,比如以1为最长递增子序列结尾元素时,其最长递增子序列长度为1,表中第一个元素就记录为1。以4为最长递增子序列结尾元素时,其最长递增子序列长度为2,表中第2个元素就记录为2。此时有两个问题需要注意:
       1>动态规划表的第一个元素默认值是1。
       2>怎么利用之前表中记录的最长递增子序列值,来推导出当前位置的最长递增子序列值?其实就是将当前位置的元素与之前位置的元素比较,如果>之前位置的元素,递增子序列长度就是在之前位置的长度+1,否则就是1,然后取较大值即可。
      接下来按上面第一章节介绍的步骤来解该问题:
       1>划分阶段
        该问题阶段的划分是按元素来的,一个元素就是一个阶段。该结果所要进行的事就是将某个元素与之前位置的所有元素进行比较。
       2>确定状态
        该问题中状态的定义是:以该位置的元素结尾,最长公共子序列的长度是多少。
       3>写状态转移方程
        状态转移的实现方式,其实在上面已有介绍,就是当某个位置的元素大于之前位置的元素时,就取之前的最长公共子序列长度+1和默认公共子序列长度之中的较大值。示例代码如下:

    				if(array[i] > array[j]){  
    					currentLegnth = Math.max(currentLegnth, dp[j]+1);
    				}
    

        当某位置的元素小于之前位置的所有元素时,以该位置元素结果的最终递增子序列长度就是默认值1。
       4>寻找边界条件
        该问题的起始条件是1,也就是以最初始位置元素为结尾的默认递增子序列长度是1,结束条件就是将元素比较完。
      示例代码如下:

    public class LongestSequence {
    	
    	public static void main(String[] args) { 
    		int[] array ={2,3,1,5,4};
    		int result = getResult(array);
    		System.out.println("最长递增子序列长度是:"+result);
    	}
    	
    	private static int getResult(int[] array){
    		int[] dp = new int[array.length];
    		dp[0] = 1;
    		for(int i = 0; i < array.length; i++){
    			int currentLegnth = 1;
    			for(int j = i-1; j >= 0; j--){
    				if(array[i] > array[j]){  
    					currentLegnth = Math.max(currentLegnth, dp[j]+1);
    				}
    			}
    			dp[i] = currentLegnth;
    		}
    		
    		int maxLength = 1;
    		for(int i = 0; i < array.length; i++){
    			System.out.println("dp["+i+"]:"+dp[i]);
    			maxLength = Math.max(maxLength, dp[i]);
    		}
    		return maxLength;
    	}
    }
    

      测试结果为:

    dp[0]:1
    dp[1]:2
    dp[2]:1
    dp[3]:3
    dp[4]:3
    最长递增子序列长度是:3

    2.5 0-1背包

      背包问题也是常见的动态规划类问题,由于背包问题有很多变体,这里先介绍0-1背包。0-1背包的特点是每种物品只有一个,并且装入背包的时候,物品不能被拆分。该问题具体形式如下:有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?例如背包锁能承受的总重量是8,各物品的重量和价值情况如下:

    重量(weight)2345
    价值(value)3456

      在写解决该问题的动态规划步骤之前,我们先看看这个问题怎么解。首先,该问题的限制条件的背包所能承受的物品的重量,所以在进行每一步计算时,都要衡量一下该物品是否能装入背包。其次,在使用动态规划表时,需要考虑是用一维的dp数组,还是二维的dp数组?在此题中,需要用二维的,因为存在着两个维度的因素:背包称重和物品。在之前已经提到,动态规划表的维度一般都要比对应的元素数要+1,用来填入初始的元素值,用于后面填表。所以,在该例子中,要创建的dp数组大小为[weight+1][value+1]。某dp数组中,某一行元素值的具体意义是:当能装入该物品时,能装入的最大价值是多少。
      接下来按上面第一章节介绍的步骤来解该问题:
       1>划分阶段
        该问题中,显而易见,阶段是按能装入到几个物品来划分的。因为动态规划表dp的其中一个维度就是物品。
       2>确定状态
        在构建动态规划表时,涉及两个元素:物品和背包承重量,所以状态也肯定使用这两者来表示,即dp[i][j]。关键的是这个dp[i][j]要表示怎样的值才合适?这时需要回到问题本身,看最后求的解是什么,就能定义这个状态表示的含义了,那就是当能装入第i个物品,背包承重为j时,所能装入物品的最大价值。这是动态规划问题的难点之一,状态的定义有时并不直观。
       3>写状态转移方程
        有了状态,就要写状态转移方程了。此时,有两种情况,1是背包的承重不足以装下当前的物品,那么此时背包能装入的最大重量是前一个物品装入的价值,用代码表示为:

    dp[i][j] = dp[i - 1][j];
    

        当背包能装入一个物品时,就需要考虑:是否要装入该物品?如果装入该物品后,不能达到最大装入价值,此物品肯定也是不需要装入的,反之则需要装入。用代码表示为:

    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    

       4>寻找边界条件
        此问题的起始变量为0,即一个物品也不装入时,背包中的物品价值为0。结束条件即物品遍历完毕。
      示例代码如下:

    public class ZeroOnePackage {
    	public static void main(String[] args) { 
    		
    		/*商品的重量2、3、4、5*/
    	    int[] weight = { 0 , 2 , 3 , 4 , 5 };  
    	    /*商品的价值3、4、5、6*/
    	    int[] value = { 0 , 3 , 4 , 5 , 6 };  
    	    /*背包限重*/
    	    int bagVeight = 8;                            
    	             
    	    int result = getMaxValue(weight,value,bagVeight);
    	    System.out.println("背包能装入的最大重量是:"+result);
    
    	}
    	
    	private static int getMaxValue(int[] weight,int[] value,int bagVeight){
    		int[][] dp = new int[weight.length][bagVeight+1];
    	    for (int i = 1; i <= 4; i++) {
    	        for (int j = 1; j <= bagVeight; j++) {
    	            if (j < weight[i])
    	                dp[i][j] = dp[i - 1][j];
    	            else
    	                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    	        }
    	    }
    	 
    	    /*输出动态规划表*/
    	    System.out.println("0-1背包问题,对应的动态规划表为:");
    	    for (int i = 0; i < 5; i++) {
    	        for (int j = 0; j < 9; j++) {
    	        	System.out.print(dp[i][j]+" ");
    	        }
    	        System.out.println();
    	    }
    	    return dp[weight.length-1][bagVeight];
    	}
    }
    

      测试结果如下:

    0-1背包问题,对应的动态规划表为:
    0 0 0 0 0 0 0 0 0
    0 0 3 3 3 3 3 3 3
    0 0 3 4 4 7 7 7 7
    0 0 3 4 5 7 8 9 9
    0 0 3 4 5 7 8 9 10
    背包能装入的最大重量是:10

    2.6 完全背包

      该问题与上一个0-1背包问题类似,所以可以直接写出类似的动态转换方程:

    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]*k] + value[i]*k);
    

      其中,k代表物品个数,k的取值范围满足的条件是:

    1=<k<=[capcity/c(i)] ,V为总可用容量,是w的最大值

      但是,如果这样实现的话,就要写三层for循环,实例代码如下:

    	public static void main(String[] args) { 
    	    int[] value={5,8};
    	    int[] weight={5,7};
    	    int capcity = 10;
    	
    	    int[][] dp = new int[value.length + 1][capcity + 1];
    	    for (int i = 0; i < value.length; i++){
    	        for (int j = 0; j <= capcity; j++){
    	            for (int k = 0; k * weight[i] <= j; k++){
    	                dp[i+1][j] = Math.max(dp[i+1][j], dp[i][j-k * weight[i]] + k * value[i]);
    	            }
    	        }
    	    }
    	    System.out.println("最大价值为:" + dp[value.length][capcity]);
    	}
    

      用三层for循环的话,时间复杂度高,代码并不美观。所以可以想办法把后两个条件结合在一起,写成一个循环条件。示例如:

    for(int c=weight[n];c<=capcity;c++)
    

      这样修改之后,除了将后两个判断条件合成一个之外,还有一个特殊的地方是:将物品个数n也融入了该判断条件。这样的话,在创建动态规划表时,就不用创建二维的表,创建一维表也能达到目的。示例代码如下:

    public class WholePackage {
        
        public static void main(String[] args) {
        	/*背包容量*/
            int capcity = 20;
            /*物品重量*/
            int weight[]={2,3,4,5,9};
            /*物品价值*/
            int value[]={3,4,5,8,10}; 
            /*物品个数*/
            int num = weight.length;
            int result = getMaxValue(weight,value,capcity,num);
            System.out.println("能装入的最大价值为:"+result);
    
        }
         
        public static int getMaxValue(int[] weight,int[] value,int capcity,int num){
            int dp[] = new int[capcity+1];
            for(int n=0;n<num;n++){
                for(int c=weight[n];c<=capcity;c++){
                	System.out.println("当前重量为:"+c);
                	dp[c] = Math.max(dp[c],dp[c-weight[n]]+value[n]);
                }
            }
            
    	    /*输出动态规划表*/
    	    System.out.println("完全背包问题,对应的动态规划表为:");
    	    for (int i = 0; i < capcity+1; i++) {
    	        	System.out.print(dp[i]+" ");
    	    }
            
            return dp[capcity];
        }
    }
    

      测试结果如下:

    完全背包问题,对应的动态规划表为:
    0 0 3 4 6 8 9 11 12 14 16 17 19 20 22 24 25 27 28 30 32 能装入的最大价值为:32

    展开全文
  • 近期笔者会一些博客,与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。...

    1.序

    近期笔者会写一些博客,与大家共同讨论一些经典的算法思想。这篇文章主要介绍动态规划算法的基本思想、使用动态规划算法求解问题的基本步骤、动态规划算法的两个基本要素以及一些经典的动态规划问题。

    2.动态规划的基本概念[^1]

    在学习动态规划之前,先思考这样一个问题:什么是动态规划?为什么叫动态规划?
    当读者在试图探索这个问题的时候,不可避免的要了解动态规划的产生背景。动态规划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学家R.E.Bellman等人提出的,应用于工程领域。
    动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。

    所谓多阶段决策过程是指这样一类决策过程:它可以把一一个复杂问题按时间(或空间)分成若干个阶段,每个阶段都需要作出决策,
    以便得到过程的最优结局。由于在每阶段采取的决策是与时间有关的而且前一阶段采取的决策如何,不但与该阶段的经济效果有关,
    还影响以后各阶段的经济效果,可见这类多阶段决策问题是一个动态的问题,因此,处理的方法称为动态规划方法。然而,动态
    规划也可以处理一些本来与时间没有关系的静态模型,这只要在静态模型中人为地引入“时间”因素,分成时段,就可以把它看作
    是多阶段的动态模型,用动态规划方法去处理。
    

    简言之,多阶段决策过程是指这样的一类特殊的活动过程:问题可以按时间顺序分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。
    下面举例说明什么是多阶段决策问题。
    例1(最短路线问题)在线路网络图1中,从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离,为使总运费最少,必须找出一条由A至E总里程最短的路线。
    在这里插入图片描述

    图1

    为了找到由A至E的最短线路,可以将该问题分成A—B—C—D—E 4个阶段,在每个阶段都需要作出决策,即在A点需决策下一步到B1还是到B2或B3;同样,若到达第二阶段某个状态,比如B1 ,需决定走向C1还是C2 ;依次类推,可以看出:各个阶段的决策不同,由A至E的路线就不同,当 从某个阶段的某个状态出发作出一个决策,则这个决策不仅影响到下一个阶段的距离,而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策,使这些决策序列所决定的一条路线对应的总路程最短。

    3.动态规划算法的基本思想[^2]

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题。
    在这里插入图片描述

    图2

    但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。
    如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法。
    在这里插入图片描述

    图3

    4.动态规划的求解步骤[^2]

    a. 找出最优解的性质,并刻划其结构特征。
    b. 递归地定义最优值。
    c. 以自底向上的方式计算出最优值。
    d. 根据计算最优值时得到的信息,构造最优解

    5.动态规划算法的基本要素[^2]

    5.1 最优子结构

    • 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质
    • 在分析问题的最优子结构性质时,所用的方法具有普遍性:首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾。
    • 利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。

    注意:同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的求解速度更快(空间占用小,问题的维度低)

    5.2 重叠子问题

    • 递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。这种性质称为子问题的重叠性质。
    • 动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果。
    • 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间,从而获得较高的解题效率。
      在这里插入图片描述
      图4

    6.一些经典的动态规划问题

    题目描述:
    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

    示例 1:

    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。
    

    示例 2:

    输入: "cbbd"
    输出: "bb"
    

    分析:
    一个问题要使用动态规划求解,一定要满足【最优子结构】,只有满足最优子结构,才能通过子问题的解 构造出 整个问题的解。

    在编码时,一般采用【备忘录】或 dp table来实现。
    最关键的要找出:该问题的递推关系式(状态转移方程)

    假设dp[i][j]=true,表示字符串s从s[i]到s[j]的子串为最长回文子串
    反之false.

    考虑 abcba 这个示例。如果我们已经知道 bca 是回文,那么要判断 abcba 是不是回文串,只需判断它的左首字母和右尾字母是否相等。这里左=右=a,因此abcba 是回文串

    从这里我们可以归纳出状态转移方程
    dp[i][j] = true
    前提是
    dp[i+1][j-1]为true,且 s[i] == s[j]

    #include <iostream>
    using namespace std;
    class MySolution {
    public:
        string longestPalindrome(string s) {
    
            int len = s.size();
            if (len < 2)
                return s;
            //bool dp[len][len];
            bool** dp;
            dp = new bool* [len];
            for (int i = 0; i < len; i++)
                dp[i] = new bool[len];//分配了len行len列的二维数组空间
        
            int max_len=1;//最大回文串长度
            int max_left;//最长回文串的起始位置
            for (int j = 0; j < len; j++)
            {
                for (int i = 0; i < j; i++)
                {
                    if (s[j] != s[i])
                        dp[i][j] = false;
                    else if (j - i < 3) // (j-1)-(i+1)+1< 2 即表明dp[i][j]是回文串
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];//s[i]==s[j]
                    if (j - i + 1 > max_len && dp[i][j])
                    {
                        max_len = j - i + 1;
                        max_left = i;
                    }
    
                }
            }
            return s.substr(max_left, max_len);
            // 用完要释放:
            for (int i = 0; i < len; i++)
            {
                delete[] dp[i]; 
                delete[]dp;
            }   
        }
    };
    int main()
    {
        MySolution sl;
        string s = sl.longestPalindrome("abcdedcabcdefggfedcba");
        cout << s << endl;
    }
    

    参考文献
    [1] 引用自百度文库https://wenku.baidu.com/view/c0f9fb156c175f0e7cd1377d.html
    [2]引用自老师的课件

    展开全文
  • 动态规划思想分析——经典题目

    千次阅读 2016-09-11 14:56:33
    动态规划思想是算法设计中很重要的一个思想,所谓动态规划就是“边走边看”,前面的知道了,后面的根据前面的也就可以推出来了。和分治算法相似又不同,相同的是都需要去寻找最优子结构,重复子问题,边界条件。不同...

    动态规划思想是算法设计中很重要的一个思想,所谓动态规划就是“边走边看”,前面的知道了,后面的根据前面的也就可以推出来了。和分治算法相似又不同,相同的是都需要去寻找最优子结构,重复子问题,边界条件。不同的是动态规划算法存储前面算得的每一个结果,后面的结果由前面的结果推倒得出。而分治则是分而治之,把问题分开解决,再合并。不存在前后两个状态之间的转换关系(想想快速排序和LCS即可想到),快速排序法就是分治的一个典型应用。通俗来说,动态规划本质上来说还是规划,是不断进行决策的问题,一般用于求解最(优)值;而分治是一种处理复杂问题的方法,不仅仅只用于解决最值问题。

    先来看动态规划,这是五大算法思想中最重要也是很常用的一个,在以后的blog中,我会慢慢地更新其他四种算法思想的分析。

    动态规划有以下几个重要方面的组成:

    1.最优子结构:如果问题的最优解包含的子问题的解也是最优的,就称该问题具有最优子结构

    2.重叠子问题你找到的最优子结构我们要将其转化为重叠子问题,用相同的方法循环求解

    3.状态转换方程:你找到的每一个子问题都可以认为是一个状态下的规划问题,而状态与状态之间你需要找到关联方程,这样我们才能从最简单的状态循环求解出所需要求解的较复杂的状态

    4.边界条件:即子问题的初值,你必须给出规模较小的一些子问题的初值来开启循环,否则无法循环求解

    4.子问题独立:独立问题,主要是子问题各对象的独立,不要发生一个子问题在操作时修改了另一个子问题中的变量的情况,具体可见我的递归模式的思考一文

    5.无后效性:某个阶段状态一旦确定就不再受后续状态决策的影响。即某状态之后的过程不会影响以前的状态,只与当前状态有关

    其中问题具有最优子结构可以分解为重复子问题无后效性这是想使用DP的问题所必须具备的性质


    ----------------------------------我是分割线~---------------------------------


    本文先介绍一类动态规划的常见问题——串与序列(串必须连续,序列可以不连续)

    1. 最长公共子序列(LCS):

    重叠子问题(以后称为状态):设数组dp[m][n]来表示长度为m的str1和长度为n的str2的最长公共子序列长度

    状态转换方程:if(str1[m]==str2[n])   dp[m][n]=dp[m-1][n-1]+1;        

        if(str1[m]!=str2[n])    dp[m][n]=max(dp[m-1][n],dp[m][n-1]);

    边界条件(初始条件):dp[i][0]=0  dp[0][j]=0   0<=i<=m      0<=j<=n

    满足 最优子结构 以及 无后效性

    2.最长公共子字符串(LCS):

    状态:设数组dp[m][n]来表示以str1[m]结尾的str1和以str2[n]结尾的str2的最长公共子字符串长度,最长的长度为dp[m][n]中最大的元素值

    状态转换方程:if(str1[m]==str2[n])   dp[m][n]=dp[m-1][n-1]+1;        

        if(str1[m]!=str2[n])    dp[m][n]=0;

    初始条件:dp[i][0]=0  dp[0][j]=0   0<=i<=m      0<=j<=n

    满足 最优子结构 以及 无后效性

    3.最长递增子序列(LIS):

    LIS问题可以使用排序+LCS问题完成,还可以用动态规划,这些时间复杂度为n2

    状态:设数组dp[m]为以a[m]结尾的序列中的最长递增序列的长度,最终的LIS长度为dp数组中的最大值

    状态转换方程:dp[i]:     for(int j=1;j<i;j++){ if(a[j-1]<=a[i-1]&&dp[j]>max)   max=dp[j]; } dp[i]=max+1;

    初始条件:dp[0]=0;

    满足 最优子结构 以及 无后效性

    4.编辑距离问题:

    状态:设edit[m][n]为长度为m的str1和长度为n的str2的编辑距离

    状态转换方程:if(j>i) edit[i][j]=edit[i][i]+j-i; else if(j<i) edit[i][j]=edit[j][j]+i-j; elseif(str1.charAt(i-1)==str2.charAt(j-1)) edit[i][j]=edit[i-1][j-1]; else edit[i][j]=edit[i-1][j-1]+1;}

    初始条件:for(int i=0;i<=m;i++) edit[i][0]=i;          for(int j=0;j<=n;j++)   edit[0][j]=j;


    -------------------------------------------------下面两个问题并不是DP问题,但也是串/序列问题------------------------------------------


    5.判断是否为子序列:boolean isSubSeq(String str1,String str2)

    6.判断是否为子字符串:contains(String str)方法:这个问题没有想象的那么简单,涉及到KMP算法,有关于KMP算法我会在之后讲解


    -----------------------------------------------------------------------下面为程序---------------------------------------------------------------------


    上面给出的六个问题,下面的均用java来实现之,其中问题3给出了两种方法,因为DP有点慢为n2复杂度,给出的新方法为nlogn复杂度!

    import java.util.logging.Logger;
    
    public class Soulution {
    	//1. 最长公共子序列(LCS):
    	public static int LCS(String str1,String str2){
    		int m=str1.length();
    		int n=str2.length();
    		int[][] dp=new int[m+1][n+1];
    		//if(str1.charAt(i)==str2.charAt(j)) dp[i][j]==dp[i-1][j-1]+1;
    		//else dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    		for(int i=1;i<=m;i++){
    			for(int j=1;j<=n;j++){
    				if(str1.charAt(i-1)==str2.charAt(j-1)) 
    					dp[i][j]=dp[i-1][j-1]+1;
    				else
    					dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
    			}
    		}
    		return dp[m][n];
    	}
    	//2.最长公共子字符串(LCS):
    	public static int LCString(String str1,String str2){
    		int m=str1.length();
    		int n=str2.length();
    		int longest=0;
    		int[][] dp=new int[m+1][n+1];  // 表示长度为mn的两个子串的lcs
    		for(int i=1;i<=m;i++){
    			for(int j=1;j<=n;j++){
    				if(str1.charAt(i-1)==str2.charAt(j-1))
    					dp[i][j]=dp[i-1][j-1]+1;
    				else
    					dp[i][j]=0;
    				longest=Math.max(longest, dp[i][j]);
    			}
    		}
    		return longest;
    	}
    	//3.最长递增子序列(LIS):动态规划n2解法
    	public static int LISDP(int[] a){
    		int[] dp=new int[a.length+1];
    		int res=0;
    		for(int i=1;i<a.length+1;i++){
    			int max=0;
    			for(int j=1;j<i;j++){
    				if(a[j-1]<=a[i-1]&&dp[j]>max)
    					max=dp[j];
    			}
    			dp[i]=max+1;
    			if(res<dp[i])
    				res=dp[i];
    		}
    		return res;
    	}
    	//3.最长递增子序列(LIS)nlogn解法:
    	
    	//LIS有动态规划和LCS转LIS(排序+LCS)两种 n2方法,还有一个nlogn方法如下:
    	//构造一个LIS(本身不是原本的LIS),保证最末位。
    	static int len=0;
    	public static int LIS(int[] arr){
    		int[] lis=new int[arr.length];
    		lis[0]=arr[0];  //目前LIS序列长度为1,末尾为arr[0]
    		len=1;
    		for(int i=1;i<arr.length;i++){
    			if(arr[i]>=lis[len-1]){
    				lis[len]=arr[i];
    				len++;
    			}
    			else{		
    				lis[binarysearch(lis, arr[i])]=arr[i];
    			}
    		}
    		return len;
    	}
    	private static int binarysearch(int[] a,int key){
    		int left=0;
    		int right=len-1;
    		int mid=(left+right)/2;
    		while(left<right){
    			mid=left+(right-left)/2;
    			if(a[mid]<key)
    				left=mid+1;
    			else
    				right=mid;
    		}
    		return left;//right is also ok
    	}
    	//4.编辑距离问题:
    	public static int editdis(String str1,String str2){
    		int m=str1.length();
    		int n=str2.length();
    		int[][] edit=new int[m+1][n+1]; // 防止低端越界以及特殊情况i
    		for(int i=0;i<=m;i++)
    			edit[i][0]=i;
    		for(int i=0;i<=n;i++)
    			edit[0][i]=i;
    		for(int i=1;i<=m;i++){
    			for(int j=1;j<=n;j++){   // 把这里的j写成i是很常见的一个错误
    				if(j>i) edit[i][j]=edit[i][i]+j-i;
    				else if(j<i) edit[i][j]=edit[j][j]+i-j;
    				else {
    					if(str1.charAt(i-1)==str2.charAt(j-1))
    						edit[i][j]=edit[i-1][j-1];
    					else
    						edit[i][j]=edit[i-1][j-1]+1;
    				}
    			}
    		}
    		return edit[m][n];
    	}
    	//5.判断是否为子序列
    	public static boolean isSubSeq(String str1,String str2){
    		int pointer1=0;
    		int pointer2=0;
    		while(pointer1<str1.length()&&pointer2<str2.length()){
    			if(str1.charAt(pointer1)==str2.charAt(pointer2))
    				pointer2++;
    			if(pointer2==str2.length()) return true;
    			pointer1++;
    		}
    		return false;
    	}
    	public static void main(String[] args){
    		//测试程序:判断是否为子串!
    		System.out.println("abcsdf".contains("abcd"));
    		//测试程序:判断是否为子序列!
    		System.out.println(isSubSeq("abscdljjkjkefg", "abcdefg"));
    		//测试程序:输出最长公共子序列的长度
    		System.out.println(LCS("abscljjkjkefg", "abcdefg"));
    		//测试程序:输出最长递增子序列LIS nlogn
    		int[] a={1,4,6,2,3,5,7};
    		System.out.println(LIS(a));
    		//测试程序:输出最长递增子序列LISDP n2
    		System.out.println(LISDP(a));
    		//测试程序:输出最长公共子字符串长度
    		System.out.println(LCString("abscljjkjkdefg", "abcdefg"));  //3
    		//测试程序:编辑距离
    		System.out.println(editdis("kitten", "sitting"));  //3
    		
    		//int[] b={1,2,6};
    		//System.out.println(binarysearch(b,3));
    	}
    }
    


    如有不足,还望大家指出~

    展开全文
  • 动态规划算法思想解决找零钱问题

    万次阅读 2017-10-16 14:20:54
    这里这篇博客的初衷很简单,就是为了方便自己,回过头来捡起这个知识能快一点,接受起来更易理解点;他人的文章的再好,毕竟是别人的,学习起来总有一定的困难。想法上,理解上总有一些不同的地方。所以在解决这...

    前言

        关于找零钱问题,网上已经有很多相关的资料以及优秀的文章博客等。这里写这篇博客的初衷很简单,就是为了方便自己,回过头来捡起这个知识能快一点,接受起来更易理解点;他人的文章写的再好,毕竟是别人的,学习起来总有一定的困难。想法上,理解上总有一些不同的地方。所以在解决这个问题后,记录下我的笔记。

    一、动态规划(DP)

        1.1 概念

        动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法

    说明:上面是对该术语的简单解释,不是算法分析与设计中对动态规划的定义。本人对算法的认识比较浅显解释这个还是很困难的,而书本上概念性的知识我认为并不适合去学习理解。当然关于动态规划定义在1.5动态规划的理解中有详细介绍。

        1.2 性质

        动态规划一般用来处理最优解的问题。使用动态规划算法思想解决的问题一般具有最优子结构性质和重叠子问题这两个因素。

    <1> 最优子结构

         一个问题的最优解包含其子问题的最优解,这个性质被称为最优子结构性质 

    <2> 重叠子问题

         递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

        1.3 基本步骤

    <1> 找出最优解的性质,并刻划其结构特征。

    <2> 递归地定义最优值。

    <3> 以自底向上的方式计算出最优值。

    <4> 根据计算最优值时得到的信息,构造最优解。

        1.4 动态规划与分治法

        动态规划和分治法有相似之处,都是将待解决问题分解为若干子问题。不同之处,分治法求解时有些子问题被重复计算了许多次;动态规划实现了存储这些子问题的解,以备子问题重复出现,当重叠子问题出现,找到已解决子问题的解即可,避免了大量的重复计算。

        1.5 动态规划的理解(来源:知乎)

        这里引用知乎王勐对动态规划的理解来作为动态规划的引入。

     

        动态规划是对于 某一类问题 的解决方法!!重点在于如何鉴定“某一类问题”是动态规划可解的而不是纠结解决方法是递归还是递推!

        当你企图使用计算机解决一个问题是,其实就是在思考如何将这个问题表达成状态(用哪些变量存储哪些数据)以及如何在状态中转移(怎样根据一些变量计算出另一些变量)。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少,所谓时间复杂度就是从初始状态到达最终状态中间需要多少步!

    一个问题是该用递推、贪心、搜索还是动态规划,完全是由这个问题本身阶段间状态的转移方式决定的!每个阶段只有一个状态->递推;

        每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心;

        每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索;

        每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

    每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到

        这个性质叫做最优子结构;

    而不管之前这个状态是如何得到的

     

    二、找零钱问题

        2.1 问题描述

        在现实生活中,经常遇到找零问题,假设有数目不限的面值为1元,5角,1角的硬币。给出需要找零金额,求出找零方案,要求:使用的硬币数目最少。

    找零钱问题:

        假设只有 1 分、 2 分、五分、 1 角、二角、 五角、 1 元的硬币。在超市结账时,如果需要找零钱,收银员希望将最少的硬币数找给顾客。那么,给定需要找的零钱数目,如何求得最少的硬币数呢?

        2.2 问题分析

    <1> 将硬币种类封装到数组 int coinsValues[]中,此处即

        int[] coinsValues = {1,2,5,10,20,50,100};
    coinsValues[i] 表示第 i 枚硬币的面值为 coinsValues[i] ,单位:分。
    coinsValues.length 表示硬币的种类

    说明

        为了使问题总有解,一般有一枚面值为 1 的硬币,此处已有。

    <2> 设 

        chargeOptimalSolution[coinKind][money]

    表示可用第0、1、2...coinKind 种硬币对找零金额 money 找零

    时所需要的最少硬币数。即当前问题的最优解。

    • coinKind 硬币种类,用来表示第几种硬币
    • money 当前找零总金额

    <3> 对于某一种硬币来说,我们可以使用该种硬币进行找零,也可以不使用该种硬币进行找零。

    于是根据当前逻辑分析,写出下面两个方法

        chargeOptimalSolution[coinKind - 1][money]
        chargeOptimalSolution[coinKind][money - coinsValues[coinKind - 1]] + 1
    • chargeOptimalSolution[coinKind - 1][money]

    表示使用第 coinKind 种硬币的情况下找零所需的最少硬币数

    • chargeOptimalSolution[coinKind][money - coinsValues[coinKind]] + 1

    表示不使用第 coinKind 种硬币的情况下找零所需的最少硬币数,因为使用了该种硬币一次,最少硬币数 chargeOptimalSolution[][] 加一。

    <4> 最优解则为二者情况中较小的一个

        //使用第 i(coinkind) 种硬币时所需的最小硬币数-- 递推 --
        //不使用第 i(coinkind) 种硬币找零时需要的最小硬币数-- 递推 --
        int numberByCoinKind = chargeOptimalSolution[coinKind - 1][money];
        int numberNotByCoinKind = chargeOptimalSolution[coinKind][money - coinsValues[coinKind-1]] + 1;
        //逻辑判断硬币数目选其中较小的
        chargeOptimalSolution[coinKind][money] =
             numberByCoinKind < numberNotByCoinKind ? numberByCoinKind : numberNotByCoinKind;

    <5> 特殊情况

        以上业务逻辑,基本上就解决了这个问题。下面说说特殊情况。

    • (1)边界问题:

    不存在对金额不为 0 的情况下找零的硬币种类为 0 ;这不就是摆明了不想找钱给顾客,黑店啊。

    不存在对币种不为 0 的情况下对找零金额为 0 的进行找零;这不就是摆明了送钱吗,赔本生意。

    对找零金额 money (money != 0),可用硬币种类为 0 种,不找钱了?

        chargeOptimalSolution[0][money]

    对找零金额为 0,可用硬币coinKind (coinKind != 0),有钱任性,送钱了,顾客一脸茫然。

        chargeOptimalSolution[coinKind][0]
    • (2)可用币种面值大于找零金额的情况

    收银员收费后需要找零 5 角,找了一张面值 50 元的面币,还干不干了这生意。

        coinsValues[coinKind] > money

    <6>综上
        找零问题的解决点就在下面这个公式:

        最优解(最少硬币数) = min{chargeOptimalSolution[coinKind - 1][money], chargeOptimalSolution[coinKind][money - coinsValues[coinKind]] + 1}

    min{a, b} 表示 a, b 中最小的那个数。

        2.3 代码实现

        ChargeProblem.Java

    package common.test;
    
    import java.util.Arrays;
    /**
     * 
     * @since 2017-10-16
     * @author niaonao
     *
     */
    public class ChargeProblem {
        
    	/**
    	 * 通过面值为 coinsValues[i] 的硬币对金额 chargeMoney 找零
    	 * @param coinsValues 硬币面值coinsValues[i],硬币面值种类数量coinsValues.length
    	 * @param chargeMoney 找零金额
    	 * @return 最小找零硬币数目
    	 */
        public static int charge(int[] coinsValues, int chargeMoney){
        	int coinsKinds = coinsValues.length;
            int[][] chargeOptimalSolution = new int[coinsKinds + 1][chargeMoney + 1];
            
            //当找零金额为 0 时,不需要找零,最少找零硬币数量为 0
            for(int i = 0; i <= coinsKinds; i++)
            	chargeOptimalSolution[i][0] = 0;
            
            //当找零金额不为 0 时,找零硬币种类不可为 0 
            for(int i = 0; i <= chargeMoney; i++)
            	chargeOptimalSolution[0][i] = Integer.MAX_VALUE;
            
            //money 找零金额; coinKind 硬币种类,用来表示第几种硬币
            for(int money = 1; money <=chargeMoney; money++){
                for(int coinKind = 1; coinKind <= coinsKinds; coinKind++){
                    
                	//找零金额小于当前硬币面值
                	if(money < coinsValues[coinKind-1]){
                		chargeOptimalSolution[coinKind][money] = chargeOptimalSolution[coinKind - 1][money];
                        continue;
                    }
                    
                    //不使用第 i(coinkind) 种硬币找零时需要的最小硬币数-- 递推 --
                	//使用第 i(coinkind) 种硬币时所需的最小硬币数-- 递推 --
                	int numberByCoinKind = chargeOptimalSolution[coinKind - 1][money];
                	int numberNotByCoinKind = chargeOptimalSolution[coinKind][money - coinsValues[coinKind-1]] + 1;
                    
                    //逻辑判断硬币数目选其中较小的
                	chargeOptimalSolution[coinKind][money] = 
                			numberByCoinKind < numberNotByCoinKind ? numberByCoinKind : numberNotByCoinKind;
                }
            }
            
            return chargeOptimalSolution[coinsKinds][chargeMoney];
        }
        
        public static void main(String[] args) {
            //初始化硬币种类数组
        	int[] coinsValues = {1,2,5,10,20,50,100};
            Arrays.sort(coinsValues);
            //初始化找零金额为625
            int chargeMoney = 625;
            int minCoinsNumber = charge(coinsValues, chargeMoney);
            System.out.println("给定找零金额" + chargeMoney
            		+ ",收银员最少的找零硬币数为" + minCoinsNumber);
        }
    }

        2.4 运行结果

     

    展开全文
  • 动态规划   实例和运行结果 对应的数组M Java关键代码: /*计算最优值方法 * Knapsack(数量n,背包容量c,重量列表w,价值列表v,数组M){} * return:无 * 说明:计算并构建0-1最优值M数组 ...
  • 应用动态规划思想解决实际问题

    千次阅读 2017-04-01 11:08:13
    应用动态规划的思想解决实际问题--“数字三角形”和“LCS”
  • 动态规划有两种基本思路,一种是自顶而下的备忘录算法,一种思路是自底向上的动态规划算法。
  • 分治时间复杂度虽然更高,但我还是了一遍加深对这种思想的理解:将一个问题分治成若干个小的同样思路的子问题来解决。本题将所求序列等分成左右两个子序列,愿序列的最大子序列和必是左序列最大子序列和,有序列最...
  • 探索动态规划的基本思想 什么问题可以用动态规划解决? 存在最优子结构,子问题相互独立。 遇到找不到最优子结构时,可以适当变换问题思路再来寻找。 巧妙的抓住,最值 这个关键字。 解决动态规划问题可尝试的基本...
  • JDK动态代理以及Cglib动态代理其实底层实现原理都是字节码的重组,不过各自对应的代理场景不同,本文我们重点研究jdk动态代理。 通过前文的了解,我们已经知道在JDK动态代理中是JDK动态的帮我们生成一个名为$Proxy0...
  • Java动态代理+注解体现Spring AOP思想

    千次阅读 2017-07-31 15:48:52
    在MVC的架构中,优秀的代码是Service业务层只做业务逻辑处理,如果要添加新功能...使用JAVA的动态代理技术,这里体现了Spring AOP切面编程的思想。 1. 什么是动态代理?查理论能查几页纸,这里简单总结一句话:调用Pr
  • 将cglib动态代理思想带入Android开发

    千次阅读 2017-05-08 23:34:35
    动态代理在Android实际开发中用的并不是很多,但在设计框架的时候...我们今天来看看这个代理究竟是什么样子,在Android开发中如何使用它,以及将cglib动态代理思想在Android中看看如何实现。项目地址:MethodIntercept
  • 首先,本博客为原创作品,欢迎指导,随意转载,如果可以请转载时说明出处,附上...动态规划算法的基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题...
  • 常见的算法思想(整理)

    千次阅读 2018-04-29 00:09:23
    子问题联系的 动态规划 算法思想 基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种...
  • 算法设计思想

    千次阅读 2016-02-06 21:15:44
    (二)动态规划算法 1.基本思想: (1)与分治法类似,也是将待求解的问题分解为若干个子问题,按顺序求解子问题,前一子问题的解,为后一子问题的求解提供了有用的信息;依次解决各子问题,最后一个子问题就是初始...
  • 背包问题与动态规划的基本思想

    万次阅读 2013-10-24 20:11:15
    网上有很多关于背包问题和动态规划的代码实现文章,但是如何理解动态规划的思想才是最关键的,尤其如何理解成这是一个多阶段的决策过程尤为重要,下面的这个动态规划讲解非常好,主要从两个思路来讲解动态规划,一个...
  • 近期刚开始接触spring-activiti工作流,并运用于实际项目中,此处记录相关思想可做以后参考。 1. 统一服务执行入口,spring-activiti的ExecutionListener为多实例: spring-activiti中监听器,我们可以统一一个...
  • 《Spring设计思想》AOP设计基本原理

    万次阅读 多人点赞 2016-04-10 20:36:07
    当我们在某个类Foo中好了一个main()方法,然后执行 java Foo ,你的Java程序之旅就开启了,如下: public class Foo { public static void main(String[] args) { // your codes begins here } } ...
  •  动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。  动态规划法与分治法和贪心法类似...
  • 动态规划原理

    千次阅读 2019-05-28 16:04:19
    动态规划通过拆分问题,将问题拆分成许多的子问题,定义问题状态和状态之间的关系(即状态转移方程或递推公式),使得问题能够以递推(或者说分治)的方式去解决。按顺序求解子问题,前一子问题的解,为后一子问题的...
  • 动态规划——解决最优问题

    千次阅读 2019-03-02 00:58:26
    说到动态规划,这里先简单看下另一个算法“贪心算法-greedy algorithm”,是一种在每一步选择中都采用在当前状态下最优或最好的选择,从而导致结果是最好或最优的算法。也就是,在当前情况下,我们只管按照“心最贪...
  • 当数组中每个元素都只带有一...使用数组的方式大规模处理数据信息,那么,如何运用动态数组呢? 动态数组是指在声明时没有确定数组大小的数组,即忽略圆括号中的下标;当要用它时,可随时重新指出数组的大小。使用动
  • Android 动态代理以及利用动态代理实现 ServiceHook

    万次阅读 多人点赞 2017-02-25 20:44:15
    // 这里死路径为 D 盘,可以根据实际需要去修改 System. out .println(paths); FileOutputStream out = null ; try { //保留到硬盘中 out = new FileOutputStream(paths+proxyName+ ".class" )...
  • 看动画轻松理解「递归」与「动态规划」

    千次阅读 多人点赞 2019-11-13 15:53:22
    程序员小吴打算使用动画的形式来帮助理解「递归」,然后通过「递归」的概念延伸至理解「动态规划」算法思想。 什么是递归 先下定义:递归算法是一种直接或者间接调用自身函数或者方法的算法。 通俗来说,递归算法的...
  • 动态规划解决数字三角形

    千次阅读 多人点赞 2020-03-18 16:21:30
    由已知推未知大法 算法思想: 由上面可以看出,存最优解的二维数组的最后一行就是原来数组的最后一行的值,而且一个元素都是可以由该元素的正下方元素和右下方元素推出来,刚好可以根据最后一层元素,层层递推,...
  • 前端组件化思想

    万次阅读 多人点赞 2018-02-27 09:59:14
      先说说为什么要这篇文章吧:不知从什么时候开始,大家相信前端摩尔定律:“每18个月,前端难度会增加一倍”。我并不完全认可这个数字的可靠性,但是这句话的本意我还是非常肯定的。   是的,前端越来越简单...
  • 从斐波那契数列理解动态规划

    千次阅读 2020-02-20 16:08:29
    一提到动态规划,大多数人都想到许许多多高端的名词,如什么状态转移方程什么的;要不就想到教材书上严谨而又晦涩难懂的对于动态规划的介绍;也有人想到高中的通项公式或数列题等等。然后脑子就开始晕了,感觉其他的...
  • (自适应动态规划综述)

    千次阅读 2020-01-08 09:36:49
    (自适应动态规划综述) 摘要:自适应动态规划(Adaptive/Approximate Dynamic Programming,ADP)是最优控制领域新兴起的一种近似最优方法,它在人工智能领域、强化学习、人工神经网络、模糊系统、演化计算等方面蓬勃...
  • 五大算法设计思想

    万次阅读 多人点赞 2018-05-12 10:18:38
    思想策略: 对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解...
  •  动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略  基本思想与分治...

空空如也

空空如也

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

思想动态怎么写

友情链接: Photoshop.rar