【原】动态规划

1、分治算法之最大子数组问题

1. 前言

本节内容是分治算法系列之一：最大子数组问题，主要讲解了什么是最大子数组问题，如何利用分治算法解决最大子数组问题，给出了最大子数组的实现伪代码并进行分析，并用 java 语言进行了伪代码实现，帮助大家通过最大子数组问题更好地理解分治算法思想的应用。

2. 什么是最大子数组问题？

最大子数组（Max Subarray）问题，是计算机科学与技术领域中一种常见的算法问题，主要可以利用分治思想进行快速实现。

最大子数组问题描述如下：假如我们有一个数组，数组中的元素有正数和负数，如何在数组中找到一段连续的子数组，使得子数组各个元素之和最大。

最大子数组问题在生活中有很多实际情况可以与其对应，比如说我们观察某一股票在一段时间内的走势，请问如何找出在哪一天买入，哪一天卖出可以赚到最大差价（这里假设你已经知道股票的价格走势）？为了实现最大化的股票收益，我们需要考虑的是买进和卖出时候的价格变化幅度，因此从该股票的每日变化幅度来考虑这个问题更加合适。所以，我们可以将这个问题稍作变形：将股票价格走势对应为每日股票价格涨跌，涨记为正值，跌记为负值，然后一段时间就对应一个正负数数组，并试图找到该数组的最大子数组，就可以获得最大收益。

接下来，就让我们看看如何利用分治算法求解最大子数组问题吧。

3. 分治法求解最大子数组问题

在最大子数组问题之后，我们一起来看一下如何利用分治思想求解最大子数组问题。这里我们假设待初始的数组为 [12, -3, -16, 20, -19, -3, 18, 20, -7, 12, -9, 7, -10]，记为数组 A，并用 A [low,high] 表示这个数组，其中 low，high 是这个数组的最小最大下标， low = 0，high = A.length -1 , 然后我们需要找到该数组的其中某一个最大子数组。

Tips: 这里我们需要注意，同一数组的最大子数组可能有多个，所以我们在这里求解的时候只说求解某一个最大子数组。

3.1 分治算法求解思路

在这里，我们用分治算法求解最大子数组问题，主要思路如下：

1. 步骤 1：

   找到数组 A 的中间元素，其下标记为 mid，根据分治策略，将数组 A [low,high] 根据中间元素划分为 A [low,mid]， A [mid+1,high] 两个部分；

2. 步骤 2：

   假设数组 A 的最大子数组为 A [i, j]，那么 A [i, j] 只有以下三种可能：

   a: 最大子数组 A [i, j] 完全位于 A [low, mid] 中，此时有 low <= i <= j <= mid;

   b: 最大子数组 A [i, j] 完全位于 A [mid+1, high] 中，此时有 mid+1 <= i <= j <= high;

   c: 最大子数组 A [i, j] 跨域了中间元素，则 low <= i <= mid <= j <= high。

   分别计算上述三种对应的最大子数组的结果；

   Tips: 在这里，情况 a 和情况 b 这两种情况所得的子问题和之前求解数组 A 的最大子数组的问题形式完全一样，这里是分治思想的主要体现，将大的问题拆分成了两个相同形式的小问题；情况 c 这时候可以直接求解，在 3.2 节中会具体介绍其求解过程。

3. 步骤 3

   对步骤 2 三种情况的求解结果进行比较，其中最大子数组的结果为最大值的情况就是我们的所求结果。

3.2 求解思路详解

首先，我们将 3.1 节中的求解思路用下图表示：

如图，我们可以更清楚地明白求解一个数组的最大子数组问题就是对 3.1 节中的步骤 2 中的三种情况的分别求解， 步骤 2 中的情况 a 和情况 b 可以通过递归求解得出结果，所以我们现在先看一下情况 c 的具体求解过程。情况 c 的求解很容易在线性时间内就可以得出结果，他并不是原问题的一个规模更小的实例，因为情况 c 中加入了一个限制（求出的子数组必须跨越下标为 mid 的中间节点）。如上图的右边图形所示，情况 c 的求解结果都会有两个子数组 A [i,mid] 和 A [mid+1,j] 组成，其中 low <= i <= mid <= j <=high。因此，我们只需要找出形如 A [i,mid] 和 A [mid+1,j] 的最大子数组，然后将其合并即可。

我们用下面的伪代码 FindMaxCrossSubarray 描述 3.1 节中 步骤 2 中的情况 c 具体实现过程：

FindMaxCrossSubarray(A, low, mid ,high):
   leftSum = minInteger; //设置左边的最大连续和初始值为最小整数值
   sum =0;
   maxLeft = mid; //记录左边最大子数组的下标位置,初始化为mid
   for (i=mid; i>=low; i--){
       sum = sum + A[i];
       if (sum > leftSum){
           leftSum = sum;
           maxtLeft = i; 
       }
   }
   rightSum = minInteger; //设置右边的最大连续和初始值为最小整数值
   sum = 0;
   maxtRight = mid + 1; //记录右边最大子数组的下标位置,初始化为mid+1
   for (j=mid+1; j<=low; j++){
       sum = sum + A[j];
       if (sum > rightSum){
           rightSum = sum;
           maxtRight = j;//记录左边最大子数组的下标位置
       }
   }
   //返回结果是一个三元组数据，分别是最大子数组的开始下标，结束下标，求和的值
   return (maxLeft,maxRight,leftSum+rightSum);  
代码块1234567891011121314151617181920212223

上述伪代码的描述中的第 2 至第 11 行，是求解左半部分 A [low,mid] 的最大子数组的过程，因为必须包含下标为 mid 的元素，所以从下标为 mid 的中间节点开始逐步递减到下标为 low 的元素，对应伪代码中的第 5 至第 11 行的 for 循环结构，循环的过程中会记录下左边部分的最大子数组的具体值及左半部分的下标位置。同理，上述伪代码的第 12 至第 21 行对应的是求解右半部分 A [mid+1,high] 的最大子数组的过程。最后，伪代码中的第 23 行综合左右两边求解结果，返回必须跨越下标为 mid 的中间元素时，对应的原数组 A 的最大子数组结果。

当我们可以清楚地知道步骤 2 中的情况 c 的求解过程时，我们就可以综合知道对于数组 A 求解最大子数组的整体过程，用伪代码 FindMaxSubarray 描述如下：

FindMaxSubarray(A,low,high):
     if (high == low){
            return new Result(low,high,A[low]);  //基础情况，只有一个元素时候的处理情况
     }else {
         //对应2.1节中步骤1，找到中间元素
         int mid = (low + high)/2;
         //对应2.1节中步骤2，分别对应a,b,c三种情况求解最大子数组结果
         (leftLow,leftHigh,leftSum) = FindMaxSubarray(A,low,mid);
         (rightLow,rightHigh,rightSum) = FindMaxSubarray(A,mid+1,high);
         (crossLow,crossHigh,crossSum) = FindMaxCrossSubarray(A,low,mid,high);
         //对应2.1节中步骤3，比较得出最后结果
         if(leftSum >= righSum && leftSum >= crossSum){
                return (leftLow,leftHigh,leftSum);
         }else if (rightSum >= leftSum && rightSum >= crossSum){
                return (rightLow,rightHigh,rightSum);
         }else {
                return (crossLow,crossHigh,crossSum);
         }
     }
代码块12345678910111213141516171819

上述求解数组 A 的最大子数组的整体过程伪代码，主要就是由我们在 2.1 节中描述的三大步骤而来。代码第 2 至第 4 行，主要表明了最基础的情况的处理方式。代码第 4 至第 18 行对应着具体的实现方式，第 8 行和第 9 行分别是对子问题的递归求解，第 10 行调用 FindMaxCrossSubarray 过程，求解跨越中间节点的最大子数组求解方式，最后第 12 至 18 行对比三种情况的结果得出最终结果。

4.JAVA 代码实现

在说明求解最大子数组的整个过程之后，接下来，我们看看如何用 java 代码实现最大子数组问题的求解。

package divide_and_conquer;
public class MaxSubarray {
    //内部类，用来存储最大子数组的返回结果，
    private static class Result {
        int low;
        int high;
        int sum;
        public Result(int low, int high, int sum) {
            this.low = low;
            this.high = high;
            this.sum = sum;
        }
        @Override
        public String toString() {
            return "Result{" +
                    "low=" + low +
                    ", high=" + high +
                    ", sum=" + sum +
                    '}';
        }
    }
    private static Result FindMaxCrossSubarray(int[]A,int low, int mid, int high){
        //寻找左边的连续最大值及记录位置
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        int maxLeft = mid;
        for (int i=mid; i>=low; i--){
            sum = sum + A[i];
            if(sum > leftSum){
                leftSum = sum;
                maxLeft = i;
            }
        }
        //寻找右边的连续最大值及记录位置
        int rightSum = Integer.MIN_VALUE;
        int maxRight = mid+1;
        sum = 0;
        for ( int j=mid+1; j<=high;j++){
            sum = sum + A[j];
            if(sum > rightSum){
                rightSum = sum;
                maxRight = j;
            }
        }
        //返回跨越中间值的最大子数组结果
        return new Result(maxLeft,maxRight,leftSum + rightSum);
    }
    public static  Result FindMaxSubarray(int[] A, int low, int high){
        //数组只有一个元素时的处理情况
        if (high == low){
            return new Result(low,high,A[low]);
        }else {
            //对应思路中步骤1，找到中间元素
            int mid = (low + high)/2;
            //对应思路中步骤2，分别对应a,b,c三种情况求解最大子数组结果
            Result leftResult = FindMaxSubarray(A,low,mid);
            Result rightResult = FindMaxSubarray(A,mid+1,high);
            Result crossResult = FindMaxCrossSubarray(A,low,mid,high);
            //对应步骤3，比较
            if(leftResult.sum >= rightResult.sum && leftResult.sum >= crossResult.sum){
                return leftResult;
            }else if (rightResult.sum >= leftResult.sum && rightResult.sum >= crossResult.sum){
                return rightResult;
            }else {
                return crossResult;
            }
        }
    }
    public static void main(String[] args){
        int[] A = {12, -3, -16, 20, -19, -3, 18, 20, -7, 12, -9, 7, -10};
        System.out.println(FindMaxSubarray(A,0,A.length-1).toString());
    }
}
代码块123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384

运行结果如下：

Result{low=6, high=9, sum=43}
代码块1

运行结果中的 low 表示最大子数组在数组 A 中的开始下标，high 表示最大子数组在数组 A 中的终止下标，sum 表示最大子数组的求和值，对应到我们的实例数组 A 中，对应的最大最大子数组为 [18,20,-7,12]。

代码中第 5 行至 25 行的 Result 内部类，主要是用来存储最大子数组的返回结果，定义了子数组的开始下标，结束下标，求和值。代码的第 27 至 55 行是最大子数组跨越中间节点时候的最大子数组求解过程。代码的第 58 至 78 行是整个最大子数组的求解过程。代码的第 81 行和 82 行是求解最大子数组过程的一个示例，输出最大子数组的求解结果。

本节主要学习了利用分治思想求解最大子数组问题，学习本节课程需要熟悉分治算法的算法流程，知道分治算法在解决最大子数组时的实现思路，可以自己用代码实现最大子数组问题的求解。在学习完本节课程之后，我们通过最大子数组这一实例介绍了分治算法的实际应用，帮助大家可以更好地理解分治算法。

2、动态规划介绍

1. 前言

本节内容是动态规划算法系列之一：动态规划的介绍，主要介绍了动态规划的定义，什么样的问题适合用动态规划算法去求解，最后说明动态规划算法在日常生活中的应用场景。

2. 什么是动态规划？

动态规划（Dynamic Programming）在数学上属于运筹学的一个分支，是求解决策过程 （decision process）最优化的数学方法，同时也是计算机科学与技术领域中一种常见的算法思想。

动态规划算法与我们前面提及的分治算法相似，都是通过组合子问题的解来求解原问题的解。但是两者之间也有很大区别：分治法将问题划分为互不相交的子问题，递归的求解子问题，再将他们的解组合起来求解原问题的解；与之相反，动态规划应用于子问题相互重叠的情况，在这种情况下，分治法还是会做很多重复的不必要的工作，他会反复求解那些公共的子问题，而动态规划算法则对相同的每个子问题只会求解一次，将其结果保存起来，避免一些不必要的计算工作。

Tips: 这里说到的动态规划应用于子问题相互重叠的情况，是指原问题不同的子问题之间具有相同的更小的子子问题，他们的求解过程和结果完全一样。

动态规划算法更多的时候是用来求解一些最优化问题，这些问题有很多可行解，每个解都有一个值，利用动态规划算法是希望找到具有最优值的解。接下来，就让我们具体看看动态规划算法的求解思路及相关应用场景。

3. 动态规划算法求解分析

3.1 适用问题

首先，在利用动态规划算法之前，我们需要清楚哪些问题适合用动态规划算法求解。一般而言，能够利用动态规划算法求解的问题都会具备以下两点性质：

1. 最优子结构： 利用动态规划算法求解问题的第一步就是需要刻画问题最优解的结构，并且如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。因此，判断某个问题是否适合用动态规划算法，需要判断该问题是否具有最优子结构。

Tips: 最优子结构的定义主要是在于当前问题的最优解可以从子问题的最优解得出，当子问题满足最优解之后，才可以通过子问题的最优解获得原问题的最优解。

1. 重叠子问题： 适合用动态规划算法去求解的最优化问题应该具备的第二个性质是问题的子问题空间必须足够” 小 “，也就是说原问题递归求解时会重复相同的子问题，而不是一直生成新的子问题。如果原问题的递归算法反复求解相同的子问题，我们就称该最优化问题具有重叠子问题。

Tips: 在这里，我们需要注意是，与适用动态规划算法去求解的问题具备重叠子问题性质相反，前面我们介绍的分治算法递归解决问题时，问题的子问题都是互不影响，相互独立的，这个也是我们在选用动态规划算法还是分治法解决问题时的一个判断条件。

3.2 算法步骤

在明确什么样的问题适合用动态规划算法去求解时，我们需要掌握动态规划算法的求解步骤：

步骤 1： 刻画一个最优解的结构特征

适合用动态规划算法求解的问题需要满足最优子结构的特征，所以在应用动态规划算法时的第一步就是刻画问题最优解的结构，一般都是用一些数学方法去描述求解问题，用数学公式表明最优解的结构特征。

步骤 2： 递归的定义最优解的值

当应用动态规划算法求解问题时，一般我们会递归的求解相同的子问题，这个时候，我们就需要去递归的定义最优解的值，通常也是先用数学公式去递归定义。

步骤 3： 计算最优解的值

当我们可以清楚的刻画一个最优解的结构特征及可以递归的定义出最优解的值之和，一般我们就可以采用自底向上的方法逐步去计算每一个最优解的值，大问题的最优解的值依赖于小问题的最优解的值，这个是动态规划算法的核心思想。

步骤 4: 利用计算出的信息构造一个最优解

前面的步骤 1,2,3 是动态规划算法求解问题的基础，如果我们仅仅需要一个最优解的值，而不是需要了解最优解本身，我们可以不用去执行步骤 4；如果我们需要了解最优解的具体情况，我们就需要在执行步骤 3 的时候维护一些额外的信息，以便用来构造出一个最优解。

4. 动态规划的应用场景

在日常的生活学习中，递动态规划算法一般可以用来解决很多实际问题。现在，我们就来看看动态规划算法具体有哪些应用场景。

动态规划示例问题：爬楼梯

假设你现在正在爬楼梯，一共需要经过 n 阶楼梯你才可以到达楼顶。每次你可以爬 楼梯的 1 或 2 个台阶。请问一共有多少种不同的方法可以爬到楼顶？

现在，让我们按照动态规划算法的求解步骤我们来分析一下这个问题：

步骤 1： 刻画爬楼梯问题一个最优解的结构特征

情况 1：输入 n=1；输出为 1解释 1：有一种情况可以爬上楼顶， 爬 1 步，记为 1

情况 2：输入 n=2；输出为 2解释 2：有两种情况可以爬上楼顶，分别为连续两次爬一阶楼梯和一次爬两阶楼梯，记为 1+1，2

情况 3：输入 n=3；输出为 3解释 3：有三种情况可以爬上楼顶，如情况 1 和 2 描述一样，记为 1+1+1,2+1,1+2

通过分析可以知道，爬楼梯问题主要在于我们可以一次爬两步或者一步，所以到达最后一阶楼梯 n 时，我们可以从第 n-2 阶楼梯爬两步或者第 n-1 楼梯爬一步完成。当我们需要知道最多有多少种方法可以爬上 n 阶的楼梯时，我们需要分别知道爬上第 n-2 阶楼梯最多有多少种方法，爬上第 n-1 阶楼梯最多有多少种方法，然后爬上第 n 阶楼梯的最多方法数量等于爬上第 n-1 阶楼梯最多的方法数量加上爬上第 n-2 阶楼梯最多的方法数量。

Tips: 在这里，我们可以发现爬楼梯问题满足第 3 节我们定义的动态规划算法需要具备的两种性质，其中的最优子结构就是：爬上 n 阶楼梯的最多方法数包含爬上第 n-1 楼梯和第 n-2 阶楼梯的最多方法数；重叠子问题：需要反复的计算爬各阶楼梯的最多方法数。

步骤 2： 递归的定义爬 n 阶楼梯最多的方法数

• 上 1 阶台阶：有 1 钟方法；

• 上 2 阶台阶：有 1+1 和 2 两种方法；

• 上 3 阶台阶：到达第 3 阶的方法总数是到达第 1 阶和第 2 阶方法的总和；

• 上 n 阶台阶：到达第 n 阶的方法总数就是到第 (n-1) 阶和第 (n-2) 阶的方法数之和。

综上所述，我们可以知道爬 n 阶楼梯的状态转移方程可以定义为：goStep (n) = goStep (n-1)+goStep (n-2)。动态规划算法最重要的就是去定义这个状态转移方程，通过这个状态转移方程我们就可以很清楚的去计算。

步骤 3： 计算爬 n 阶楼梯最多方法数的值

楼梯阶数 n	爬 n 阶楼梯最多的方法数
1	1
2	2
3	goStep(1)+goStep(2)=1+2=3
4	goStep(2)+goStep(3)=2+3=5
5	goStep(3)+goStep(4)=3+5=8
6	goStep(4)+goStep(5)=5+8=13
7	goStep(5)+goStep(6)=8+13=21
8	goStep(6)+goStep(7)=13+21=36
9	goStep(7)+goStep(8)=21+36=57

步骤 4： 利用计算出的信息构爬 n 阶楼梯每次走几步的方法

其实在爬楼梯这个问题中，我们并不需要统计每次的具体爬楼梯方法，如果需要统计每次具体走法时，需要在计算的时候记录之前的每一步走法，把信息全部记录保留下来即可。

我们可以很明显的发现，动态规划算法很多时候都是应用于求解一些最优化问题（最大，最小，最多，最少），这类问题在现实生活或者学习科研中经常会遇到，这是一种解决问题的思路与方法，希望大家可以好好思考。

本节主要介绍了动态规划算法的定义及基本概念，在学完本节课程之后，需要明白什么样的问题适合利用动态规划求解，如何自己去设计一个动态规划算法，以及我们日常生活中哪些应用场景适合用动态规划思想解决问题。

3、动态规划之钢条切割问题

1. 前言

本节内容是动态规划算法系列之一：钢条切割问题，主要讲解了什么是钢条切割问题，如何利用动态规划算法解决钢条切割问题，给出了钢条切割问题的实现伪代码并进行分析，并用 Java 语言进行了伪代码实现，帮助大家通过钢条切割问题更好的理解动态规划算法思想的应用。

2. 什么是钢条切割问题？

我们来考虑现实生活中的一个实际应用场景，某个钢材公司购买长钢条，将其切割为短钢条出售，其中切割过程本身不考虑成本，公司管理层想知道最赚钱的钢材切割方案。假设我们知道该钢材公司出售一段长度为 i 米的钢条的价格为 p (i)，对应的价目表如下：

i	1	2	3	4	5	6	7	8	9	10
p(i)	1	5	8	9	10	17	17	20	24	30

所以，钢材切割问题的定义如下：当我们给定一段长度为 n 米的钢条和对应的一个价格表（ p (i), i = 1,2,3,…n)，求一个钢条切割方案，使得最终的销售收益 r (n) 最大。（在这里，我们要求切割的钢条必须为整米长度）

接下来，就让我们看看如何利用动态规划算法求解钢条切割问题吧。

3. 动态规划算法求解钢条切割问题

在应用动态规划算法之前，我们先来看一下应该如何去表示一段长度为 n 米的钢材切割问题。首先，我们可以很清楚的知道一段长度为 n 米的钢条一共有 2n-1 种切割方案，因为在钢条的第 1,2,3，…，n-1 米的位置，我们均可以选择切割或者不切割。对于一段长度为 n 米的钢条，假设我们将他切割为 k 段，每一长度段记为 i1，i2，…，ik 米，我们可以将切割方案记为 n= i1+i2+…+ik，对应的收益 r (n) = p (i1) + p(i2) +… + p(ik)。接下来，我们按照上一节介绍的动态规范算法的求解步骤来求解钢条切割问题。

1. 步骤 1: 刻画一个钢条切割最优解的结构特征

根据之前描述的，在钢条的第 1,2,3，…，n-1 米的位置，我们均可以选择切割或者不切割。现在我们考虑将一段长度为 n 米钢材切割的最大收益 r (n) 用小一点的钢材收益表示，假设这个时候我们可以选择切割一次或者不切割，那对应着的 n 米的钢材会有 n 种处理方案，分别为：{p (n)，r (1)+r (n-1), r (2)+r (n-2),…,r (n-2)+r (2),r (n-1)+r (1)}，这里的 p (n) 表示没有切割，这样我们就可以将计算一段长度为 n 米的钢材的最优化切割方案转换为小一点长度的钢材的最优化切割方案。

在这里，我们可以注意到，为了求解规模为 n 的问题，我们先求解形式完全一样，单规模更小的问题。当完成首次切割之后，我们将两段钢材看出两个独立的钢条切割问题。我们通过组合两个相关子问题的最优解，并在所有可能的两段切割方案中选择组合收益最大者，构成原问题的最优解。我们称钢条切割问题满足最优子结构性质：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。

1. 步骤 2: 递归的定义钢条切割的最优解

当我们清楚一个钢条切割最优解的结构特征之后，现在开始递归的定义钢条切割的最优解，我们先看一下前面几种简单的钢条切割的最优解是什么样的：

r (1) = 1，钢条长度为 1 米的钢条最优切割方法就是自身，因为已经无法切割了

r (2) = 5，钢条长度为 2 米的钢条切割方案有两种， 1+1 或者 2，对应的价值分别为 2 或 5，所以 r (2)=5

r (3) = 8，钢条长度为 3 米的钢条切割方案有四种， 3,1+2,2+1，对应的价值分别为 8,6,6，所以 r (3)=8

对应步骤 1 中的钢条切割问题的最优解的结构特征，我们可以递归的定义钢条切割问题的最优解：

r(n) = max { p(n), r(1)+r(n-1), r(2)+r(n-2),…,r(n-2)+r(2), r(n-1)+r(1)}

除了上述的钢条最优切割问题的最优解的定义之外，钢条切割问题还可以以另外一种相似的但是更为简单的方法去求解：将钢条左边切割下长度为 i 米的一段，只对右边剩下的长度为 n-i 的一段进行继续切割（递归求解），对左边的一段则不再进行切割。此时，问题可以分解为：将长度为 n 的钢条分解为左边开始一段以及剩余部分继续分解的结果。这样，我可以得到对于上面公式的一个简化版本：

r(n) = max { p(i) + r(n-i) } , 1<= i <= n

至此，我们已经完成了递归的定义钢条切割问题的最优解；接下来，我们开始计算最优解的值。

1. 步骤 3： 计算钢条切割最优解的值

考虑到对于长度为 n 的钢条切割的最优解由其子问题决定，我们可以先求解长度较小的钢条切割的最优解，然后用较小长度的最优解去逐步求解长度较大的钢条切割的最优解。相关伪代码定义如下：

 CutSteelRod(p,n):{
     r[0...n] be a new array[]
    r[0]=0
    for (int i=1; i<=n; i++){
         q = Integer.MIN_VALUE
         for (int j=1;j<=i;j++){
             q = max(q,p[j]+r[i-j])
         }
         r[i]=q
     }
    return r[n]
 }
代码块123456789101112

算法的第 2 行定义了一个新数组 r [0…n] 用来说存储子问题的最优解，第 3 行将 r [0] 初始化为 0，因为长度为 0 的钢条没有收益。第 4 行到第 10 行是两个 for 循序，外层的 for 循环分别求解长度为 i 的钢条切割的最优解，内部的 for 循环是每一次求解最优解的具体过程。

1. 步骤 4： 利用计算出的信息构造一个钢条切割问题的最优解

前面的算法 CutSteelRod 可以计算出钢条切割问题通过动态规划算法计算出来的最优解，但是并不会返回解本身（对应的一个长度列表，给出每段钢条的切割长度），如果我们需要得出具体的解，就需要对步骤 3 中的切割算法进行重构，具体伪代码如下：

 ExtendCutSteelRod(p,n){
     r[0...n],s[0...n] be new arrays[]
     r[0]=0
     for (int i=1; i<=n; i++){
         q = Integer.MIN_VALUE
         for (int j=1;j<=i;j++){
             if(q < p[j]+r[i-j]){
                 q = p[j]+r[i-j]
                 s[i] = j
             }
         }
         r[i]=q
     }
     return r and s
 }
代码块123456789101112131415

ExtendCutSteelRod 算法与 CutSteelRod 算法很相似，只是在算法的第 2 行创建了数组 s，并在求解规模为 i 的子问题时将第一段钢条的最优切割长度 j 保存在 s [i] 中，详见算法中的第 9 行。

4.JAVA 代码实现

在说明求解钢条切割问题的整个过程之后，接下来，我们看看如何用 java 代码实现钢条切割问题的求解。

import java.util.Scanner;
public class SteelBarCutProblem {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] p = {0,1,5,8,9,10,17,17,20,24,30};
        int[] r = new int[p.length];
        int[] s = new int[p.length];
        System.out.println("请输入1到"+ (p.length-1)+"之间任意一个自然数: ");
        int n = scanner.nextInt();
        r[0] = 0;
        for(int i =1; i<=n; i++){
            int q = Integer.MIN_VALUE;
            for (int j=1; j<=i; j++){
                if(q < (p[j] + r[i-j])){
                    q = p[j] + r[i-j];
                    s[i] = j;
                }
            }
            r[i] = q;
        }
        System.out.println("长度为"+ n +"米长的钢材最大切割收益为："+r[n]);
        System.out.println("对应的具体每一段的切割长度如下：");
        while (n>0){
            System.out.println(s[n]);
            n = n - s[n];
        }
    }
代码块123456789101112131415161718192021222324252627282930313233

运行结果如下：

请输入1到10之间任意一个自然数: 
8
长度为8米长的钢材最大切割收益为：22
对应的具体每一段的切割长度如下：
2
6
代码块123456

运行结果中首先需要输入一个自然数表示要切割的钢条的长度，然后对应输出该长度钢条切割之后的最大化收益以及具体的切割方法。

代码中第 8 行至第 10 行分别初始化对应长度的钢材的价格表，对应长度钢条切割之后的最大化收益数组，对应长度钢条满足最大化收益时第一次切割的长度。代码的第 15 行至第 25 行主要来实现步骤 4 中的 ExtendCutSteelRod 算法，用来计算最大化的切割收益及保存解，代码的 27 行至 32 行主要是对求解结果的输出。并且代码中引用了 Scanner 类用来进行交换处理，可以在控制台输入一段需要切割的钢条长度，然后返回对应的切割结果。

本节主要学习了利用动态规划算法求解钢条切割问题，学习本节课程掌握钢条切割问题的算法流程，知道分动态规划算法是如何解决此类最优化问题，并且可以自己用代码实现钢条切割问题的求解。在学习完本节课程之后，我们通过钢条切割问题这一实例介绍了动态规划算法的实际应用，帮助大家可以更好的理解动态规划算法。

贪心算法

1. 前言

本节内容是贪心算法系列之一：贪心算法的介绍，主要介绍了贪心算法的定义，贪心算法的使用条件，明确了什么样的问题适合用贪心算法求解，最后说明贪心算法在日常生活中的应用场景。

2. 什么是贪心算法？

贪心算法（Greedy Algorithm）是计算机科学与技术领域中一种常见的选择算法，与之前介绍的动态规划算法有一定的相似度。

顾名思义，贪心算法总是会做出在当前情况下看来最好的选择，谓之贪心，也就是说贪心算法并不会从整体最优考虑，它所做出的选择都只是在某种意义上的局部最优选择。当然贪心算法虽然不能对所有的问题得出整体最优解，但是在很多问题中还是有着很好的应用，可以得到整体的最优解。

贪心算法与动态规划算法的最大区别在于：贪心算法每次选择的时候都是按照贪心策略来选择的，满足当前情况的最优解，但是并不一定会是整体最优解；动态规划算法在选择考虑时会考虑所有的子情况，选择最优解，这会是整体的最优解。

3. 贪心算法的使用条件

首先，在利用贪心算法求解问题之前，我们需要清楚什么样的问题适合用贪心算法求解。一般而言，能够利用贪心算法求解的问题都会具备以下两点性质：

1. 贪心选择： 当某一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次做出的选择可以依赖以前做出的选择，但不需要依赖后面需要做出的选择。这就是贪心选择性质。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

1. 最优子结构： 如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。问题的最优子结构性质是该问题是否可以用贪心算法求解的关键所在。

贪心算法与动态规划算法求解的问题类似，都需要满足最优子结构的性质。

4. 贪心算法的应用场景

在日常的生活学习中，贪心算法一般可以用来解决很多实际问题。现在，我们就来看看贪心算法具体有哪些应用场景。

场景 1：活动选择问题

假如小明是一个勤工俭学的在校生，每天可以兼职的时候有 10 个小时，然后现在学校有多个不同的兼职岗位，每个岗位有个开始时间和结束时间，小明在同一时间只能做一份兼职，请问小明每天最多可以做多少份的兼职？

面对这样的问题，其实在日常生活中，我们的第一选择肯定是先把结束时间早的兼职活动做了，然后再去做其他的兼职？这里面其实就是有贪心思想的应用，因为我们每次都是先做完结束时间早的兼职，然后我们会留出更多的时间可以做其他兼职。

这个问题里面的贪心选择就是每次选择最先结束的兼职活动，并且可以证明每次选择的最先结束的兼职活动是整体最优的，因为如果不是选择最先结束的兼职活动，剩下的可兼职的时间就少了，可以完成的兼职也就少了。同样，兼职选择活动具备最优子结构的性质，子问题可以选择的最多兼职在整体问题中同样适用。

场景 2：钱币找零问题

有 1 元、2 元、5 元、10 元的纸币分别有若干张，要用这些纸币凑出 m 元，至少要用多少张纸币？

这个是生活中最为常见的一种场景，经常我们在商场中用现金付款时，我们付出了 100 元，当收银员找零的时候，不知道大家有没有发现，收银员总是会先找零面额较大的货币，然后找零面额较小的货币，这个其实也是一个贪心选择的过程，因为这样可以保证找零的货币数量最少。

我们可以很明显的发现，贪心算法很多时候都是应用于求解一些最优化问题，与动态规划算法很相似，这类问题在现实生活或者学习科研中经常会遇到，这是一种解决问题的思路与方法，希望大家可以好好思考。

本节主要介绍了贪心算法的定义及基本概念，在学完本节课程之后，需要明白什么样的问题适合利用贪心算法求解，如何自己去设计一个贪心算法，以及我们日常生活中哪些应用场景适合用贪心算法思想求解。

5、贪心算法之活动选择问题

1. 前言

本节内容是贪心算法系列之一：活动选择问题，主要讲解了什么是活动选择问题，如何利用贪心算法解决活动选择问题，给出了活动选择问题的实现伪代码并进行分析，并用 java 语言进行了伪代码实现，帮助大家通过活动选择问题更好的理解贪心算法思想的应用。

2. 什么是活动选择问题？

假设我们现在有一个 n 个活动的集合 S={a1, a2, a3, …an}，这些活动需要使用相同一个资源，但是这个资源在某一个时刻只能被一个活动使用，并且每一个活动 ai 都有一个开始时间 si 和结束时间 fi ，其中 si < fi ，并且开始时间和结束时间都在可以选择的活动时间范围内。这里，如果某个活动 ai 被选中，则我们可以说活动 ai 发生在半开时间区间 [ si，fi ) 内，如果两个活动 ai 和 aj 满足 [ si, fi ) 和 [ sj, fj ) 不重叠，则称它们是兼容的。也就是说，若 si >= fj 或者 sj >= fi , 则称 ai 和 aj 是相互兼容的，在活动选择问题中，我们希望选出一个最大兼容活动集。

我们考虑现实生活中的一个活动选择问题实例，比如学校里面有一个大的阶梯教室，可以用来上公开课。这里这个阶梯教室就相当于是一个资源，不同的公开课，比如数学课、语文课、英语课等等，这就是一个个活动，并且每节课都有一个开始时间和结束时间，活动选择问题就要求我们选择出所有的可以在阶梯教室中安排的课程，保证选出的课程集合是一个最大的兼容活动集。

接下来，就让我们看看如何利用贪心算法解决活动选择问题。

3. 贪心算法求解活动选择问题

首先，我们假设活动以及按照结束时间的单调递增的顺序排序好，满足： f1 <= f2 <= … <= fi <= … fn，考虑的活动集合如下：

i	1	2	3	4	5	6	7	8	9	10	11
si	1	3	0	5	3	5	6	8	8	2	12
fi	4	5	6	7	9	9	10	11	12	14	16

回顾一下前一节我们在贪心算法介绍中提到的，能够应用贪心算法求解的问题需要满足两个条件：最优子结构和贪心选择，接下来，我们就具体来看看在活动选择问题中的最优子结构和贪心选择分别是什么。

3.1 最优子结构

我们假设 Sij 表示在 ai 结束之后开始，并且在 aj 开始之前结束的那些活动的集合。我们希望求得 Sij 的一个最大的相互兼容的活动子集，我们假定 Aij 就是这样的一个子集，且其中包含活动 ak 。由于最优解包含活动 ak ，我们得到两个子问题：寻找 Sik 中的兼容活动（在 ai 结束之后开始且 ak 开始之前结束的那些活动）以及寻找 Skj 中的兼容活动（在 ak 结束之后开始且 aj 开始之前结束的那些活动)。

如上所述，我们假设 c [i, j] 表示集合 Sij 的最优解的大小，则可以按照这种方式去刻画活动选择问题的最优子结构: c [i, j] = c [i, k] + c [k, j] + 1; 当然，如果我们不知道 Sij 的最优解包含活动 ak ，就需要考察 Sij 中所有活动，寻找哪个活动可以获得最优解，最终结果如下：

3.2 贪心选择

假如我们无需求解所有的子问题就可以选择出一个活动加入到最优解，这样可以使得我们省去递归考察所有选择的过程。所以在活动选择问题中，我们只需要考虑一种选择：贪心选择。

对于活动选择问题，什么是贪心选择？直观上说，我们应该选择一个这样的活动，选择它之后剩下的资源可以被尽量多的其他活动选择占用。所以，在这个活动选择问题中，我们选择最早结束的活动，这样剩下来的时间最多，剩下的资源可以供它之后尽量多的活动使用。

3.3 迭代贪心算法

按照上面分析的最优子结构和贪心选择方法，我们可以用迭代的方法去求解活动选择问题，相关伪代码如下：

GreedyActivitySelect(a,s,f):
    //定义活动总数
    n = s.length
    //按照贪心策略，首先选中第一个结束的活动
    A = {a[i]}
    //记录当前选中的活动
    k = 1
    //for循环遍历，按照贪心策略选择活动
    for i=2 to n{
        if s[i] >= f[k]{
            A = A.add(a[i])
            k = i
        }
    }
代码块1234567891011121314

其中，算法的输入是活动选择集合 a，活动选择问题的开始时间 s 和结束时间 f ，并且已经按照结束时间依次递增的顺序排序好。算法会将选择的活动存入集合 A，最后返回集合 A 作为最终选择的活动集合。

4.JAVA 代码实现

在说明求解钢条切割问题的整个过程之后，接下来，我们看看如何用 java 代码实现钢条切割问题的求解。

import java.util.ArrayList;
import java.util.List;
public class ActivitySelect {
    public static void main(String args[]){
        //活动集合a
        int a[] = {1,2,3,4,5,6,7,8,9,10,11};
        //活动开始时间集合s
        int s[] ={1,3,0,5,3,5,6,8,8,2,12};
        //活动结束集合f
        int f[] ={4,5,6,7,9,9,10,11,12,14,16};
        //活动选择存放集合A
        List<Integer> A =  new ArrayList<>();
        int n = s.length;
        A.add(a[0]);
        int k =0;
        //遍历选择活动
        for (int i=1; i<n; i++){
            if(s[i] >= f[k]){
                A.add(a[i]);
                k = i;
            }
        }
        System.out.println("活动选择问题的选择活动结果为：");
        System.out.println(A);
    }
}
代码块1234567891011121314151617181920212223242526272829303132

运行结果如下：

活动选择问题的选择活动结果为：
[1, 4, 8, 11]
代码块12

代码中第 7 行至第 14 行分别初始化活动和对应的开始时间、结束时间以及活动选择过程中存放选择的活动集合，代码的第 16 至 18 行对应着开始的活动选择初始化工作，因为 java 数组的下标从 0 开始，所以这里面我们第一个选择的活动为 a [0]，而不是伪代码中的 a [1]。代码的第 20 行至 26 行 for 循环遍历活动选择，按照贪心选择的方法选择对应的活动，放入最终的结果集 A 中 ，代码的 28 行 29 行输出相关的活动选择结果。

本节主要学习了利用贪心算法处理活动选择问题，学习本节课程掌握贪心算法解决活动选择问题的流程，知道贪心算法在解决问题时是如何考虑最优子结构及寻找贪心选择，并且可以自己用代码实现活动选择问题的求解。在学习完本节课程之后，我们通过活动选择问题这一实例介绍了贪心算法的实际应用，帮助大家可以更好地理解贪心算法。

6、贪心算法之背包问题

1. 前言

本节内容是贪心算法系列之一：背包问题，主要讲解了什么是背包问题，如何利用贪心算法解决背包问题，给出了背包问题的实现伪代码并进行分析，并用 java 语言进行了伪代码实现，帮助大家通过背包问题更好的理解贪心算法思想的应用。

2. 什么是背包问题？

假设我们一共有 n 种物品，每种物品 i 的价值为 vi，重量为 wi，我们有一个背包，背包的容量为 c（最多可以放的物品重量不能超过 c），我们需要选择物品放入背包中，使得背包中选择的物品中总价值最大，在这里每个物品可以只选择部分。这便是我们常说的背包问题

背包问题是一种常见的可以用贪心算法进行求解的问题，接下来，就让我们看看如何利用贪心算法解决背包问题。

3. 贪心算法求解背包问题

首先，这里我们考虑背包的容量为 30，并给出这个问题中我们考虑到的各类物品及对应的重量和价值，如下：

物品 n (i)	1	2	3	4	5
重量 w (i)	10	5	15	10	20
价值 v (i)	20	30	15	25	10

回顾一下我们在贪心算法介绍中提到的，能够应用贪心算法求解的问题需要满足两个条件：最优子结构和贪心选择，接下来，我们就具体来看看在背包问题中的最优子结构和贪心选择分别是什么。

首先，如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。问题的最优子结构性质是该问题是否可以用贪心算法求解的关键所在。对于背包问题，很显然它是满足最优子结构性质的，因为一个容量为 c 的背包问题必然包含容量小于 c 的背包问题的最优解的。

其次，我们需要考虑在背包问题中，我们应该按照什么样的贪心选择进行选取。很显然，如果要使得最终的价值最大，那么必定需要使得选择的单位重量的物品的价值最大。所以背包问题的贪心选择策略是：优先选择单位重量价值最大的物品，当这个物品选择完之后，继续选择其他价值最大的物品。

这里的背包问题可以用贪心算法实现，是因为背包选择放入的物品可以进行拆分，即并不需要放入整个物品，可以选择放入部分物品，我们这样的背包选择问题为部分背包问题（可以只选择物品的部分），与之对应的另一种背包问题为 0-1 背包问题，这个时候整个物品不可以拆分，只可以选择放入或者不放入，0-1 背包问题用贪心算法并不能求得准确的解，需要用动态规划算法求解。

背包问题求解详解：

在这里，我们按照优先选择单位重量价值最大的物品，所以第一步需要计算单位每个物品的单位价值，如下：

unitValue(1) = 20/10 = 2
unitValue(2) = 30/5  = 6
unitValue(3) = 15/15 = 1
unitValue(4) = 25/10 = 2.5
unitValue(5) = 10/20 = 0.5
代码块12345

所以我们有：

unitValue(2) > unitValue(4) > unitValue(1) > unitValue(3) > unitValue(5)
代码块1

当考虑背包的容量为 30 时， 我们发现可以按照物品的单位价值进行依次放入，直至背包容量放满或者物品放完为止，放入的过程如下：

物品类型	放入重量	背包使用容量	背包剩余容量
2	5	5	25
4	10	15	15
1	10	25	5
3	5	30	0

按照如上步骤我们简单分析了一下背包问题的求解过程，接下来，我们看一下如何用代码实现背包问题。

4.JAVA 代码实现

在说明求解背包问题的整个过程之后，接下来，我们看看如何用 java 代码实现背包问题的求解。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Knapsack {
    /**
     * 物品内部类
     */
    private static class Item implements Comparable<Item>{
        int type;
        double weight;
        double value;
        double unitValue;
        public Item(int type, double weight){
            this.type = type;
            this.weight = weight;
        }
        public Item(int type, double weight,double value){
            this.type = type;
            this.weight = weight;
            this.value = value;
            this.unitValue = value/weight;
        }
        @Override
        public int compareTo(Item o) {
            return Double.valueOf(o.unitValue).compareTo(this.unitValue);
        }
    }
    public static void main(String[] args){
        //背包容量
        double capacity = 30;
        //物品类型初始化数组
        int[] itemType = {1,2,3,4,5};
        //物品重量初始化数组
        double[] itemWeight = {10,5,15,10,30};
        //物品价值初始化数组
        double[] itemValue = {20,30,15,25,10};
        //初始化物品
        List<Item> itemList = new ArrayList<>();
        for(int i=0;i<itemType.length;i++){
            Item item = new Item(itemType[i],itemWeight[i],itemValue[i]);
            itemList.add(item);
        }
        //物品按照单价降序排序
        Collections.sort(itemList);
        //背包选择
        List<Item> selectItemList = new ArrayList<>();
        double selectCapacity = 0;
        for(Item item : itemList){
            if( (selectCapacity + item.weight) <= capacity){
                selectCapacity = selectCapacity + item.weight;
                Item selectItem = new Item(item.type,item.weight);
                selectItemList.add(selectItem);
            }else {
                Item selectItem = new Item(item.type, capacity-selectCapacity);
                selectItemList.add(selectItem);
                break;
            }
        }
        //选择结果输出
        for (Item item : selectItemList){
            System.out.println("选择了类型："+ item.type+" 的物品，重量为："+item.weight);
        }
    }
}
代码块1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374

运行结果如下：

选择了类型：2 的物品，重量为：5.0
选择了类型：4 的物品，重量为：10.0
选择了类型：1 的物品，重量为：10.0
选择了类型：3 的物品，重量为：5.0
代码块1234

代码中第 10 行至第 31 行定义了物品的一个内部类，用来存储一个物品的类型、重量、价值、单位重量的价值，并且实现在其中实现了一个对比函数。代码的第 35 至 42 行对应着开始的背包问题的初始化工作，分别初始化了背包容量、物品类型、物品重量、物品价值。代码的第 44 行至 51 行将所有物品按照物品内部类的格式加入数组，并且按照物品单位重量的价值进行降序排序。代码的第 53 行至第 66 行，按照背包问题的贪心选择方法选择对应的物品，并记录选择的物品类型及重量，放入到选择的物品列表中 ，代码的 69 行 71 行输出相关的物品选择结果。

本节主要学习了利用贪心算法处理背包问题，学习本节课程掌握贪心算法解决背包问题的流程，并且可以自己用代码实现背包问题的求解。在学习完本节课程之后，我们通过背包问题这一实例介绍了贪心算法的实际应用，帮助大家可以更好的理解贪心算法。