To be or not to be.

简述

背包问题的一般形式是给定一组物品，每一组物品有自己的重量和价格，在限定的总重量内，如何选择才能使得物品的总价值最大。在此基础上有多种变体，比较基本的三种问题如下：

• 01背包：有n种物品，第i个物品的体积为$v_i$，价格为$w_i$，有一个体积限制v，每种物品有一个，可以选或者不选。
• 完全背包：有n种物品，第i个物品的体积为$v_i$，价格为$w_i$，有一个体积限制v，每种物品有无限个，可以选或者不选。
• 多重背包：有n种物品，第i个物品的体积为$v_i$，价格为$w_i$，有一个体积限制v，每种物品有$c_i$个，可以选或者不选。

在此基础上有时还有额外的要求，如背包必须放满。

01背包

基本思路

01背包的基本思路是所有背包问题的基础。

我们先约定记号dp[i][v]表示在空间为v的背包中，用(0...i)这i件物品能组合出的空间不超过v的物品的最大价值。

当我们在考虑第i件物品时，我们有两个选择：选取或者不选取该物品。

• 不选取第i件物品，那么意味着其实只用了(0...i-1)件物品，可以得到dp[i][v]=dp[i-1][v]
• 选取了第i件物品，那么意味着前(0...i-1)件物品占用了v-w[i]的体积，所以dp[i][v]=dp[i-1][v-c[i]] + w[i]

显然我们需要最终找到的是容量为v情形下可以取到的最大价值。但我们显然无法一蹴而就，因为根据上述描述dp[i][v]依赖于dp[i-1][v-c[i]]。因此需要从初始状态进行转移，直至推算到dp[i][v]。

初始状态

我们可以认为是背包空间为0的情况。在此情况下，无论物品如何，都无法选取任何物品，总价值为0。在此基础上，向后推算其他状态。

状态转移方程

根据基本思路中所提的转移方式，我们可以得到每个状态的转移方程如下：

复杂度及优化

根据上述定义，我们需要维护的状态为dp[1...N][0...V]，所以时间复杂度为O(VN)，空间复杂度也为O(VN)。

我们无法再优化时间复杂度，但空间复杂度仍有可以优化的地方。仔细观察上述状态转移方程，从物品的维度上来看，考虑第i件物品的最大值时，只需要参考第i-1件物品的情况，具体来说是dp[i-1][j]和dp[i-1][j-c[i]]，而和之前的物品状况都没有任何关系。因此我们只需要一个滚动的一维数组来存放状态即可。

当我们刚刚进入第i次循环的时候，对应的j和j-c[i]的位置目前仍然是dp[i-1][j]和dp[i-1][j-c[i]]。如果我们按照正向循环j的话，那么在计算j位置时，[j-c[i]]的位置在前，已经被更新过了，已经不再是dp[i-1][j-c[i]]。但如果我们从[V..0]逆向循环j，则可以保证每次计算j位置时，当前的j和j-c[i]仍然是上一轮i-1时候的值，从而达到优化的效果。

通过上述逆序迭代V，我们不再需要一个N*(V+1)的二维数组存放状态，而只需要一个大小为V+1的一维数组，从而可以将空间复杂度优化到O(1)。

初始化的细节

在背包问题中，基础情况是物品所占空间不能超过背包容量，但有时候也会要求物品重量必须恰好等于背包容量。对这两种方法需要采取不同的初始化方法。

• 未要求恰好装满背包的最优解 - 初始化时将dp[0...V]全部设为0
• 恰好装满背包时的最优解 - 在初始化时除了dp[0]为0其它f[1..V]用一个其他值标记，转移时进行特别判断

一个常数优化

在决定一个物品i是否需要纳入的时候，不需要遍历i-1时候所有V的情况，只需要知道dp[v-c[n]]即可。

完全背包问题

基本思路

不装入第i种物品，即dp[i−1][j]，同01背包； 装入第i种物品，此时和01背包不太一样，因为每种物品有无限个（但注意书包限重是有限的），所以此时不应该转移到dp[i−1][j−w[i]]而应该转移到dp[i][j−w[i]]，即装入第i种商品后还可以再继续装入第种商品。

我们先约定记号dp[i][v]表示在空间为v的背包中，用(0...i)这i件物品能组合出的空间不超过v的物品的最大价值。

初始状态也是一样的，我们将dp[0][0...W]初始化为0，表示将前0种物品（即没有物品）装入书包的最大价值为0。那么当 i > 0 时dp[i][j]也有两种情况：

当我们在考虑第i件物品时，我们有两个选择：选取或者不选取该物品。

• 不选取第i件物品，和01背包相同，dp[i][v]=dp[i-1][v]
• 选取了第i件物品，此时和01背包不太一样，因为每种物品有无限个（但注意书包限重是有限的），所以此时不应该转移到dp[i−1][j−w[i]]而应该转移到dp[i][j−w[i]]，即装入第i种商品后还可以再继续装入第种商品

状态转移方程

根据基本思路中所提的转移方式，我们可以得到每个状态的转移方程如下：

常数空间复杂度实现

我们可以看到和01背包最大的拆别在于不再是根据dp[i−1][j−w[i]，而是dp[i][j−w[i]]来推算dp[i][j]。因此我们基于01背包一维数组的解法，我们只要将j的循环顺序从倒序改为正序，每次先更新dp[i][j−w[i]]，这样当我们求解dp[i][j]时即可达到j位置仍为上一轮结果，而j-w[i]位置已经是本轮结果的效果。

可以考虑的简单优化

在解题过程中，可以考虑首先将空间大于V的物品去掉，然后计算出相同物品中价值最高的那个物品。

多重背包问题

思路1. 将物品展开，全拆成01背包求解。这与完全背包的朴素思路一致。与完全背包的情况一样，这种方法是正确的，但是时间复杂度较高。

思路2. 二进制分解 - TBD

典型问题

背包的问题常见的有三种，

• 求最值
• 体积要取到背包容量的最值
• 求方案数

322. 零钱兑换

题目

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。

示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

思路

这是一个完全背包问题。这类完全背包的题目，可以直接使用一维数组优化空间复杂度且不需要改变循环顺序。

转移方程及DP矩阵

dp[i][j] = dp[i-1][j] 不选i这种硬币
dp[i][j] = dp[i][j-coins[i]] + 1 选取i这种硬币

示例中对应的dp矩阵如下

解题

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int v = amount + 1;

        if (n == 0 || amount == 0) return 0;

        int[] dp = new int[v];
        Arrays.fill(dp, v);
        dp[0] = 0;

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

416. 分隔等和子集

题目

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200

示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

思路

因为每个数只可以用一次，因此是一道01背包题。需要看是不是存在组合的和刚好为总和的一半。 我们用dp数组记录是不是存在恰好的放满的组合，不存在记为-1，存在记为1。 但要求背包刚好放满，因此初始化的时候标记为-1，表示不可取。向后转移的时候只有在可取的子问题之后继续推。

注意本题是01背包，所以如果用一维数组进行空间复杂度优化的时候，需要反向遍历。

转移方程及DP矩阵

dp[i][j] = dp[i-1][j] 不取第i个物品
dp[i][j] = dp[i-1][j-nums[i]] == -1 ? -1 : 1 取第i个物品

解题

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0) return true;

        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        if (sum % 2 == 1) return false;
        int half = sum / 2;

        int[] dp = new int[half + 1];
        Arrays.fill(dp, -1);
        dp[0] = 1;

        for (int i = 0; i < nums.length; i++) {
            for (int j = half; j >= nums[i]; j--) {
                if (dp[j - nums[i]] != -1) {
                    dp[j] = 1;
                }
            }
        }

        return dp[half] == 1;
    }
}

474. 一和零

题目

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有5个0和3个1的最大子集是 {"10","0001","1","0"}，因此答案是4。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含4个1大于n的值3。

思路

本题是一个01背包问题，每个元素可以取或者不取，背包也不必要一定装满。主要的特点是相比于一般背包只需要考虑一个”容量“，本题需要考虑0和1两个“容量”，类似于多个随机变量的联合分布。

因此在进行了01背包的空间复杂度优化后，使用二维dp数组记录状态。循环的时候均需要倒序进行循环。

需要注意的是，01背包在不选取的时候，取dp[i-cnt0(strs[i])][j-cnt1(strs[i])]。在数组状态压缩后，取的是当前dp点，即未选取该物品的值和选取该物品的情况两者中的最大值，即：dp[j][k] = Math.max(dp[j][k], dp[j - c0][k - c1] + 1)。

另外还有一个优化，即倒序循环的时候并不需要循环直到0。所以两种循环写法等价但是第二种写法更好，时间可以从41ms提高到31ms，用时击败从76.45%提升到99.28%。

转移方程

dp[i][j] = dp[i-cnt0(strs[i])][j-cnt1(strs[i])] 不取本物品
dp[i][j] = dp[i-cnt0(strs[i])][j-cnt1(strs[i])] + 1 选取本物品

解题

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        int max = 0;

        for (int i = 0; i < strs.length; i++) {
            int c0 = cnt0(strs[i]);
            int c1 = strs[i].length() - c0;

            for (int j = m; j >= c0; j--) {
                for (int k = n; k >= c1; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - c0][k - c1] + 1);
                }
            }
        }
        return dp[m][n];
    }

    private int cnt0(String str) {
        int cnt = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '0') cnt++;
        }
        return cnt;
    }
}

518. 零钱兑换II

题目

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

思路

完全背包问题，需要求得恰好组成目标面值的组合方式。维护一个二维dp数组。其中的值代表有可能的组合方式，则dp[0]=1表示只有什么都不取这一种组合方式。且由于是完全背包，因此在用一维数组记录状态时，无需逆向进行循环。

另外注意边界情况：

• 如果amount=0，无论硬币什么情况，什么都不取即是唯一的组合，返回1
• 如果coins为空，除非amount=0，无法组合成任何值，返回0

转移方程及DP矩阵

dp[j]= dp[j] + dp[j - coins[i]]

解题

class Solution {
    public int change(int amount, int[] coins) {
        if (amount == 0) return 1;
        if (coins == null || coins.length == 0) return 0;

        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j]+= dp[j - coins[i]];
            }
        }

        return dp[amount];
    }
}

1049. 最后一块石头的重量II

题目

有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

思路

可以转化一下题目描述，其实就是求可以取到最接近sum/2的组合。 这样题目就变成了一道典型的01背包。

如果使用一维数组维护状态，因为是01背包，每个物品只能取一次

• 如果不取该物品，则跟当前位置dp[i][j]上一轮的值相同
• 如果取该物品，则跟当前位置向前数dp[i-1][j-stones[i]]有关，如果反向进行循环，则是取dp[i][j-stones[i]] + stones[i]即可，因为此时dp[i][j-stones[i]]的值还是上一轮的值

转移方程及DP矩阵

dp[i][j] = dp[i-1][j] 不取i物品
dp[i][j] = dp[i-1][j-stones[i]] + stones[i]

// 一维数组维护状态
dp[j] = max{ dp[j], dp[j-stones[i]] + stones[i]} // j 从大往小推

解题

class Solution {
    public int lastStoneWeightII(int[] stones) {
        if (stones == null || stones.length == 0) return 0;

        int sum = 0; 
        for (int s : stones) {
            sum += s;
        }

        int half = sum / 2;

        int[] dp = new int[half + 1];

        for (int i = 0; i < stones.length; i++) {
            for (int j = half; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        return sum - 2 * dp[half];
    }
}

参考

背包九讲