动态规划之背包问题

动态规划是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。动态规划往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。

动态规划

基本概念

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

基本思想与策略

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

适用的情况

能采用动态规划求解的问题的一般要具有 3 个性质：

• 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
• 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
• 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

求解基本步骤

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态；或倒过来，从结束状态开始，通过对中间阶段决策的选择，达到初始状态。

动态规划的设计都有着一定的模式，一般要经历以下几个步骤：

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

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。

实际应用中可以按以下几个简化的步骤进行设计：

1. 分析最优解的性质，并刻画其结构特征。
2. 递归的定义最优解。
3. 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。
4. 根据计算最优值时得到的信息，构造问题的最优解。

一个简单的动态规划

问题：10 节楼梯，每次只能上 1 节或者 2 节，恰好上到第 10 节有多少种上法？

可以从后往前推，上法总数 = 最后一步走 1 节的方法数 + 最后一步走 2 节的方法数。

我们定义 f[10] 为上到第 10 节的方法数，

那么显然 f[10] = f[10-1] + f[10-2] = f[9] + f[8]，

继续递推则有 f[9] = f[8] + f[7]，f[8] = f[7] + f[6]，

推广到一般形式即为 f[n] = f[n-1] + f[n-2]，

其中 2<=n<=10，初始条件为 f[0] = 1、f[1] = 1。

代码如下：

int climbStairs(int n) {
    if(n <= 1) return 1;
    int f[n+1];
    f[0] = 1;
    f[1] = 1;
    for(int i=2; i<=n; i++){
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

背包问题

01 背包问题-1

有 n 个物品，每个物品体积为正整数 A[i](1<=i<=n)，一个背包容量为正整数 m，问这个背包最多能装多少体积？

Sample Input: n = 4, A = [2, 3, 5, 7], m = 11

首先考虑最后一个体积为 7 的物品放不放？

不放：前三个物品 [2, 3, 5] 放到体积为 11 的包里，最多能放多少？

放：前三个物品 [2, 3, 5] 放到体积为（11-7=4）的包里，最多能放多少？

我们定义 f[4][11] 表示前 4 个物品放到体积为 11 的背包里，最多放的体积，

则有 f[4][11] = max(f[3][11], f[3][11-7] + 7)，

推广到一般形式即为 f[i][j] = max(f[i-1][j], f[i-1][j-A[i]] + A[i])，

其中 1<=i<=n、0<=j<=m，初始条件为 f[0][0] = 0,f[0][1] = 0, ... ,f[0][m] = 0，

时间复杂度为 O(n*m)。

若A = [3, 4, 5, 8] m = 10，其动态规划过程如下表：

代码如下：

/**
 * @param m: An integer m denotes the size of a backpack
 * @param A: Given n items with size A[i]
 * @return: The maximum size
 */
public int backPack(int m, int[] A) {
    int n = A.length;
    int[][] f = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if (j - A[i - 1] >= 0) {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - A[i - 1]] + A[i - 1]);
            }
        }
    }
    return f[n][m];
}

public int max(int a, int b){
    return a > b ? a : b;
}

01 背包问题-2

有 n 个物品，每个物品体积为正整数 A[i](1<=i<=n)，价值为 V[i]，一个背包容量为正整数 m，问这个背包最多能装多少价值？

Sample Input: n = 4, A = [2, 3, 5, 7], V = [1, 5, 2, 4], m = 11

这个问题跟前一个背包问题差不多，只是把体积换成价值而已。

首先考虑最后一个体积为 7，价值为 4 的物品放不放？

不放：前三个物品 [2, 3, 5] 放到体积为 11 的包里，最多能放多少？

放：前三个物品 [2, 3, 5] 放到体积为（11-7=4）的包里，最多能放多少？

我们定义 f[4][11] 表示前 4 个物品放到体积为 11 的背包里，最多放的价值，

则有 f[4][11] = max(f[3][11], f[3][11-7] + 4)，

推广到一般形式即为 f[i][j] = max(f[i-1][j], f[i-1][j-A[i]] + V[i])，

其中 1<=i<=n、0<=j<=m，初始条件为 f[0][0] = 0,f[0][1] = 0, ... ,f[0][m] = 0，

时间复杂度为 O(n*m)。

代码跟上题几乎完全相同，只需把 A 替换成 V 即可：

/**
 * @param m: An integer m denotes the size of a backpack
 * @param A & V: Given n items with size A[i] and value V[i]
 * @return: The maximum value
 */
public int backPackII(int m, int[] A, int V[]) {
    int n = A.length;
    int[][] f = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if (j - A[i - 1] >= 0) {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - A[i - 1]] + V[i - 1]);
            }
        }
    }
    return f[n][m];
}

public int max(int a, int b){
    return a > b ? a : b;
}

背包计数问题

有 n 个物品，每个物品体积为正整数 A[i](1<=i<=n)，一个背包容量为正整数 m，问有多少种方法可以把它装满？

Sample Input: n = 4, A = [2, 3, 5, 7], m = 11

首先考虑最后一个体积为 7 的物品放不放？

不放：前三个物品 [2, 3, 5] 放到体积为 11 的包里，有多少种方法装满？

放：前三个物品 [2, 3, 5] 放到体积为（11-7=4）的包里，有多少种方法装满？

我们定义 f[4][11] 表示前 4 个物品放到体积为 11 的背包里的方法总数，

则有 f[4][11] = f[3][11] +　f[3][11-7]，

推广到一般形式即为 f[i][j] = f[i-1][j] + f[i-1][j-A[i]]，

其中 1<=i<=n、0<=j<=m，初始条件为 f[0][0] = 0,f[0][1] = 0, ... ,f[0][m] = 0，

时间复杂度为 O(n*m)。

代码如下：

/**
 * @param m: An integer m denotes the size of a backpack
 * @param A: Given n items with size A[i]
 * @return: The maximum size
 */
public int backPack(int m, int[] A) {
    int n = A.length;
    int[][] f = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if (j - A[i - 1] >= 0) {
                f[i][j] = f[i - 1][j] + f[i - 1][j - A[i - 1]];
            }
        }
    }
    return f[n][m];
}

无限背包问题

有 n 个物品，每个物品体积为正整数 A[i](1<=i<=n)，价值为 V[i]，一个背包容量为正整数 m，问这个背包最多能装多少价值？（每个物品可以有无限多个），

Sample Input: n = 4, A = [2, 3, 5, 7], V = [1, 5, 2, 4], m = 11

首先考虑最后一个体积为 7，价值为 4 的物品放不放，放的话放多少个？

不放：前三个物品 [2, 3, 5] 放到体积为 11 的包里，最多能放多少？

放：放 k 个，前三个物品 [2, 3, 5] 放到体积为（11-k*7）的包里，最多能放多少？

我们定义 f[4][11] 表示前 4 个物品放到体积为 11 的背包里，最多放的价值，

则有 f[4][11] = max(f[3][11], f[3][11-k*7] + k*4)，其中 1<=k<=11/7，k 为整数，

推广到一般形式即为 f[i][j] = max(f[i-1][j], f[i-1][j-k*A[i]] + k*V[i])，

其中 1<=i<=n、0<=j<=m，初始条件为 f[0][0] = 0,f[0][1] = 0, ... ,f[0][m] = 0，

时间复杂度为 O(n*m^2)。

本题还有一种 O(n*m) 解法。

同样的思路，考虑首先考虑最后一个体积为 7，价值为 4 的物品放不放？

不放：前三个物品 [2, 3, 5] 放到体积为 11 的包里，最多能放多少？

放：前四个物品 [2, 3, 5, 7] 放到体积为（11-7=4）的包里，最多能放多少？

我们定义 f[4][11] 表示前 4 个物品放到体积为 11 的背包里，最多放的价值，

则有 f[4][11] = max(f[3][11], f[4][11-7] + 4)，

推广到一般形式即为 f[i][j] = max(f[i-1][j], f[i][j-A[i]] + V[i])，

其中 1<=i<=n、0<=j<=m，初始条件为 f[0][0] = 0,f[0][1] = 0, ... ,f[0][m] = 0，

时间复杂度为 O(n*m)。

参考资料

• 五大常用算法之二：动态规划算法
• 九章算法