背包问题

特点一：至少要用目标值作为一个 DP 维度

特点二：对具体元素敏感(比如 01 背包)，但对同一 totalSize / totalValue 来讲，有时候如何构造而来的具体路线不重要。这是由元素特性和背包 size 的约束条件决定的，也是有别于其他种类 DP 的一个重要区别。

  • 比如 Combination Sum IV，就是典型的 “对最终结果敏感，对元素个数不敏感” 的问题，每次可以取任意元素，任意个，因此只用 dp[sum] 一个维度做 dp 就够了。

  • 在只取 min/max 的时候我们不同的循环顺序都能保证正确答案；但是求解的数量时，要以 target value 为外循环。

这个章节覆盖的六道背包问题是非常基础的，只是讲了个皮毛，还有很多衍生泛化和混合的问题，我会在后面慢慢补充。更加系统的总结可以看一篇十年前的文章，背包九讲，这个人的水平非常高。

有一件事不太明白，这么经典的DP问题，六类动态规划之一，leetcode五六百道题里面竟然一道都没有。

不过leetcode上面倒是有一道爬梯子，可以作为intro。

70. Climbing Stairs

一共有n级台阶，每次可以跳一步或者两步，问跳到顶有多少种不同的方式？

刚学算法时还以为算法个个都是类似于这种脑筋急转弯的题，曾经还学过一个题叫扔鸡蛋，不知道几楼扔下去鸡蛋会碎的情况下每次爬楼梯扔鸡蛋，不同鸡蛋个数怎么减少爬楼梯的层数，从而确定到底哪一层会扔碎鸡蛋。那时候这类题多少给我一种胡闹的感觉，说好听点顶多算智力选拔，后来慢慢学得多了才理解这类算法题对计算机架构设计和数据内部实现深刻的影响，能把严肃晦涩的原理抽象成生动的模型也是一种功力吧。

动态规划的四要素为状态，方程，初始化和答案。

这道题，我们首先考虑最后一步，想清楚最后一步前面就全部都能推导出来。

如果要跳到第n级，我们有两种方式，一种是从n - 1级的地方跳一步，一种是从n - 2的地方跳两步。

那么，有多少种方式呢，跳到n的方案数 = 跳到n - 1的方案数 + 跳到n - 2的方案数。（状态）

我们设f[n]为跳到n的总方案数（答案），你可以把f看作一个函数，当然它实际上就是一个数组。那么，f[n] = f[n - 1] + f[n - 2]（方程）

四要素已经说了三个，最后一个初始化怎么考虑？很显然，从0级跳到0级，只有一种方案，原地不动。从0级跳到1级，也是一种方案，跳一步。

  • f[0] = 1

  • f[1] = 1

既然四要素都集齐了，就可以很轻松实现代码了。

public class Solution {
    public int climbStairs(int n) {
        int[] f = new int[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];
    }
}

Backpack I

背包问题原初系列一代目。

  • n个物品，每个物品体积A[i]，背包容量为m。

  • 均为正整数，问背包最大放多少？

这道题还是顺着上一道题的思路来想，我们考虑最后一步，最后一个物品放还是不放？

举个例子，4个物品，每个物体体积的数组为[2,3,5,7]，容量为11。

最后一个物品无非就两种情况，放和不放。

  • 不放：如果我们不放最后一个物品，那么背包的容量就不受影响，为11，那么问题就变成了：有3个物品，体积[2,3,5]，容量11。最大放多少？

  • 放：如果我们放最后一个体积为7的物品，那么背包的容量变成（11 - 7），那么问题就变成了：有3个物品，体积[2,3,5]，容量4。最大放多少？

最重要的一步来了，动态规划中最难的一个要素就是状态，状态在DP中用来中存储小规模问题的结果，状态主要靠灵感和创造力得到的，再就是经验。

因为状态界定的困难，DP问题才会这么难，FB才这么喜欢考这种坑爹问题。感觉就像是以前的数学考试答案，“我们不妨设x...”，我就想问了，凭什么？

状态：我们不妨设f[4][11]表示前4个物品放到容量为11的背包中，最大能够放的体积

根据前面的分析，可以得出：

f[4][11] = max (f[3][11] , f[3][4] + 7)

这样一来，我们方程也得到了，而答案就是f[4][11]，这没什么可说的，最后就剩下初始化了。

在这里面，f[i]只跟f[i - 1]有关，所以我们只要初始化f[0][0]到f[0][m]就行了，放0个物品时，最多永远只能放0体积。

  • f[0][0] = 0
  • f[0][1] = 0
  • ....
  • f[0][m] = 0
public class Solution {
    public int backPack(int m, int[] A) {
        int[][] f = new int[A.length + 1][m + 1];

        for (int i = 0; i <= m; ++i) {
            f[0][i] = 0;
        }
        for (int i = 1; i <= A.length; ++i) {
            for (int j = 0; j <= m; ++j) {
                f[i][j] = f[i - 1][j];
                if (A[i - 1] <= j) {
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - A[i - 1]] + A[i - 1]);
                }
            }
        }
        return f[A.length][m];
    }
}

Backpack II

01背包系列一代目。

这个是背包九讲里面的第一个背包问题。这回我们除了体积要考虑之外还多了一个价值，每一个物品的价值是不同的，求的是最大价值是多少。

有了前面的铺垫，这道题就变得非常简单，只要把上一道题的体积部分换成价值变量就可以了。也就是我们对“状态”的定义稍加改变。

状态：我们设f[4][11]表示前4个物品放到容量为11的背包中，最大能够放的价值

如此，我们有f[4][11] = max (f[3][11] , f[3][4] + 4)，注意这里面的4指的是最后一个物品的价值，而在上一题中的7指的是最后一个物品的体积。

通过一个非常微小的修改，我们就解决了一个新的问题，这是背包问题的特点，每道题看起来都很不容易去构思，解法往往有微妙的不同。

初始化：

  • f[0][0] = 0
  • f[0][1] = 0
  • ....
  • f[0][m] = 0
public class Solution {
    public int backPackII(int m, int[] a, int v[]) {
        int[][] f = new int[a.length + 1][m + 1];
        for (int i = 0; i <= m; ++i) {
            f[0][i] = 0;
        }
        for (int i = 1; i <= a.length; ++i) {
            for (int j = 0; j <= m; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= a[i - 1]) {
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - a[i - 1]] + v[i - 1]);
                }
            }
        }
        return f[a.length][m];
    }
}

Backpack III

无限背包系列一代目（反正就是一代目

和上一道题的题设差不多，就多了一个条件，就是每一个元素都可以取用无限次。

虽说是每个元素都可以取用无限次没错，但是背包的容量是有限的，那么元素用的次数也是一个有限值，我们就设这个值为k。往背包里面放多少个元素呢？放k个元素。

状态：我们设f[4][11]表示前4个物品放到容量为11的背包中，最大能够放的价值，在这其中，第四个物品放入k个。

根据前面题目的思路，我们可以得出类似的方程：

我们有f[4][11] = max (f[3][11] , f[3][11 - 7 * k] + 4 * k)

f[i][j] = max (f[i - 1][j] , f[i - 1][j - A[i - 1] * k] + V[i - 1] * k)

其他的都和上一题没有什么区别。

public class Solution {
    public int backPackIII(int[] A, int[] V, int m) {
        int[][] f = new int[A.length + 1][m + 1];

        for (int i = 0; i <= m; ++i) {
            f[0][i] = 0;
        }
        for (int i = 1; i <= A.length; ++i) {
            for (int j = 0; j <= m; ++j) {
                f[i][j] = f[i - 1][j];
                for (int k = 1; k <= j / A[i - 1]; ++k) {
                    if (j >= A[i - 1] * k) {
                        f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - A[i - 1] * k] + k * V[i - 1]);
                    }
                }
            }
        }
        return f[A.length][m];
    }
}

这种解法的时间复杂度是O(n * m ^ 2), 在某些testcase下会超时或者出错，所以我们需要一个更好的解法。一种时间复杂度为O(n * m)的解法。

既然是无限次取用元素，就意味着我们取完第i个元素，下一个还是i。

我们有f[4][11] = max (f[3][11] , f[4][11 - 7] + 4)

因为第四个有无限个，所以每次放完4之后，还是从前4个开始放。

f[i][j] = max (f[i - 1][j] , f[i][j - A[i - 1]] + V[i - 1])

时间复杂度降到了 O(n * m) ，一下就AC了。

public class Solution {
    public int backPackIII(int[] A, int[] V, int m) {
        int[][] f = new int[A.length + 1][m + 1];

        for (int i = 0; i <= m; ++i) {
            f[0][i] = 0;
        }
        for (int i = 1; i <= A.length; ++i) {
            for (int j = 0; j <= m; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= A[i - 1]) {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - A[i - 1]] + V[i - 1]);
                }
            }
        }
        return f[A.length][m];
    }
}

Backpack IV

方案数背包

将背包装满有多少种不同的方案数？

从这道题开始，研究的东西从最优问题转向了方案数问题。基本上可以说DP只适合干三件事，最优问题，比如最大值最小值，方案总数问题，而不是求具体方案，判断可行性。

其实这道题才是最贴近我们的intro，LC70爬楼梯那道题。因为都是求方案总数嘛。从最优问题转到方案数问题也非常的简单，改动很小，因为微妙的变化是背包问题的特点嘛（我自己瞎总结的特点，就是把max求最大值改为加号+，就可以了。

另外和III一样，都是无限次取用元素，所以每次取完还是i。

根据前面的思路，很容易写出方程：

f[4][11] = f[3][11] + f[3][4]

f[i][j] = f[i - 1][j] + f[i][j - A[i - 1]]

初始化又有一点点微妙的不一样，f[0][0] = 1，剩下的还是为0。因为0体积的一个背包，我们什么都不放，或者说放入0个物体的时候，应当看做背包被装满，因为0体积的背包放入不了任何物品，所以背包是满的，这种情况下就是什么都不做，方案数为1。

public class Solution {
    public int backPackIV(int[] nums, int target) {
        int[][] f = new int[nums.length + 1][target + 1];
        f[0][0] = 1;
        for (int i = 1; i <= target; ++i) {
            f[0][i] = 0;
        }
        for (int i = 1; i <= nums.length; ++i) {
            for (int j = 0; j <= target; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= nums[i - 1]) {
                    f[i][j] = f[i - 1][j] + f[i][j - nums[i - 1]];
                }
            }
        }
        return f[nums.length][target];
    }
}

Backpack V

和IV一个意思，就是变成了每一个元素只能用一次。

所以每次取完就是i - 1。

public class Solution {
    public int backPackV(int[] nums, int target) {
        int[][] f = new int[nums.length + 1][target + 1];
        f[0][0] = 1;
        for (int i = 1; i <= target; ++i) {
            f[0][i] = 0;
        }
        for (int i = 1; i <= nums.length; ++i) {
            for (int j = 0; j <= target; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= nums[i - 1]) {
                    f[i][j] = f[i - 1][j] + f[i - 1][j - nums[i - 1]];
                }
            }
        }
        return f[nums.length][target];
    }
}

思考一下，如果不要求将背包装满，有多少种方法去装呢？

没有这道题，但是作为一个follow-up的可能性还是挺高的，可以想一想，没有testcase就不写代码了。

Backpack VI / 377. Combination Sum IV

原理和 climbing stairs 差不多，建一个大小等于 target + 1 的 array 代表多少种不同的方式跳上来，依次遍历即可。

时间复杂度 O(n * target)

注意这里内外循环的顺序不能错，要先按 sum 从小到大的顺序看，然后才是遍历每个元素。因为所谓 bottom-up，是相对于 sum 而言的，不是相对于已有元素的 index 而言的。

可以看到，在只取 min/max 的时候我们不同的循环顺序都能保证正确答案；但是求解的数量时，要以 target value 为外循环。

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] f = new int[target + 1];

        f[0] = 1;

        for (int i = 1; i <= target; ++i) {
            for (int j = 0; j < nums.length; ++j) {
                if (i >= nums[j]) f[i] += f[i - nums[j]];
            }
        }
        return f[target];
    }
}

279. Perfect Squares

仔细观察一下这题:

  • 我们要凑出来一个和正好是 n 的选择组合；

  • 能选的元素是固定数量的 perfect square (有的会超)

  • 一个元素可以选多次；

这不就是背包吗

public class Solution {
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        Arrays.fill(f, n + 1);
        f[0] = 0;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j * j <= n; ++j) {
                if (i - j * j >= 0) f[i] = Math.min(f[i], f[i - j * j] + 1);
            }
        }
        return f[n];
    }
}

322. Coin Change

背包类问题的马甲题。

  • 每个元素可以取任意次；

  • 只问最小的硬币数，就类似于 climbing stairs，只靠 sum 一个维度就可以了，但是循环依然是两层。

比较直观的写法是这样(内外循环的顺序无所谓，但是最好从 amount 那个维度开始)

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        Arrays.fill(f, amount + 1);
        f[0] = 0;

        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < coins.length; ++j) {
                if (i - coins[j] >= 0) {
                    f[i] = Math.min(f[i], f[i - coins[j]] + 1);
                }
            }
        }
        return f[amount] == amount + 1 ? -1 : f[amount];
    }
}

k Sum

背包类问题的扩展版本

我们关注的维度有三个：

  • 前 i 个元素，因为一个元素只能选一次；

  • 选了 j 个元素，因为我们要求选 k 个数；

  • 总和 sum，用于每次试图添加新元素时用来查询。

时间：O(len k target)，三重循环

空间：O(k * target)

public class Solution {
    public int kSum(int A[], int k, int target) {
        // int[i][j][k] : number of ways to get sum of k by picking
        //                j numbers from first i numbers
        int[][][] dp = new int[2][k + 1][target + 1];

        dp[0][0][0] = 1;
        dp[1][0][0] = 1;

        for(int i = 1; i <= A.length; i++){
            for(int j = 1; j <= k; j++){
                for(int v = 1; v <= target; v++){
                    // i has an offset of 1, becasue when i = 1
                    // we are actually referring to index 0
                    if(v >= A[i - 1]){
                        dp[i % 2][j][v] = dp[(i - 1) % 2][j][v] + 
                                          dp[(i - 1) % 2][j - 1][v - A[i - 1]];
                    } else {
                        dp[i % 2][j][v] = dp[(i - 1) % 2][j][v];
                    }
                }
            }
        }
        return dp[A.length % 2][k][target];
    }
}

results matching ""

    No results matching ""