hinsyeow

引言

背包问题（Knapsack problem）是一类经典的组合优化的NP完全（NP-Complete, NPC）问题。该问题可描述为：给定一组物品，每个物品有各自的重量和价值，在背包总重量限制下，如何选择物品以使背包内物品的总价值最大。由于NPC问题不存在多项式时间复杂度的解法，不过借助动态规划，我们能够以伪多项式时间复杂度求解背包问题。

背包问题主要有以下几种类型：

01背包问题
完全背包问题
多重背包问题

一、01背包问题

1.1 问题描述

一共有 $N$ 件物品，第 $i$ （ $i$ 从1开始）件物品的重量为 $w [i]$ ，价值为 $v [i]$ 。在背包总重量不超过承载上限 $W$ 的情况下，求能够装入背包的物品的最大价值。

1.2 动态规划解法

1.2.1 定义状态数组

根据问题描述，我们定义二维状态数组 $d p [i] [j]$ ，其中 $i$ 表示前 $i$ 件物品， $j$ 表示背包的当前承重。 $d p [i] [j]$ 表示在前 $i$ 件物品中选择，背包承重为 $j$ 时所能获得的最大价值。

dp[i][j]

1.2.2 状态转移方程

首先，将 $d p [0] [0 d o t s W]$ 初始化为0，意味着将前0个物品（即没有物品）装入背包时，最大价值为0。当 $i > 0$ 时， $d p [i] [j]$ 有以下两种情况：

不装入第 $i$ 件物品：此时最大价值与只考虑前 $i - 1$ 件物品时相同，即 $d p [i - 1] [j]$ 。
装入第 $i$ 件物品（前提是 $j g e q w [i]$ ）：装入第 $i$ 件物品后，背包的最大价值为装入前 $i - 1$ 件物品且背包承重为 $j - w [i]$ 时的最大价值加上第 $i$ 件物品的价值，即 $d p [i - 1] [j - w [i]] + v [i]$ 。

因此，状态转移方程为：

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) // j >= w[i]

1.2.3 空间优化

由状态转移方程可知， $d p [i] [j]$ 的值仅与 $d p [i - 1] [0 d o t s j - 1]$ 有关。因此，我们可以使用滚动数组的方法对空间进行优化，将二维数组 $d p$ 优化为一维数组。需要注意的是，为了避免上一层循环的 $d p [0 d o t s j - 1]$ 被覆盖， $j$ 必须逆向枚举。优化后的伪代码如下：

// 01背包问题伪代码(空间优化版)
dp[0...W] = 0
for i = 1...N
    for j = W...w[i] // 必须逆向枚举!!!
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

此算法的时间复杂度为 $O (N W)$ ，空间复杂度为 $O (W)$ 。由于 $W$ 的值是其位数的幂，所以该时间复杂度为伪多项式时间。

二、完全背包问题

2.1 问题描述

完全背包问题（unbounded knapsack problem）与01背包问题的区别在于，每种物品的数量是无限的。即一共有 $N$ 种物品，每种物品有无限个，第 $i$ （ $i$ 从1开始）种物品的重量为 $w [i]$ ，价值为 $v [i]$ 。在总重量不超过背包承载上限 $W$ 的情况下，求能够装入背包的物品的最大价值。

2.2 动态规划解法

2.2.1 定义状态数组

与01背包问题类似，定义 $d p [i] [j]$ 表示将前 $i$ 种物品装入限重为 $j$ 的背包中所能获得的最大价值，其中 $0 l e q i l e q N$ ， $0 l e q j l e q W$ 。

2.2.2 状态转移方程

初始状态同样将 $d p [0] [0 d o t s W]$ 初始化为0。当 $i > 0$ 时， $d p [i] [j]$ 有以下两种情况：

不装入第 $i$ 种物品：即 $d p [i - 1] [j]$ ，与01背包问题相同。
装入第 $i$ 种物品：由于每种物品数量无限，装入第 $i$ 种物品后还可继续装入该种物品，因此状态应转移到 $d p [i] [j - w [i]]$ ，即 $d p [i] [j - w [i]] + v [i]$ 。

状态转移方程为：

dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]) // j >= w[i]

2.2.3 空间优化

与01背包问题不同，完全背包问题空间优化后 $j$ 必须正向枚举，因为状态转移方程中的第二项是 $d p [i]$ 而非 $d p [i - 1]$ ，需要覆盖之前的值。优化后的伪代码如下：

// 完全背包问题思路一伪代码(空间优化版)
dp[0...W] = 0
for i = 1...N
    for j = w[i]...W // 必须正向枚举!!!
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

该解法的时间复杂度为 $O (N W)$ ，空间复杂度为 $O (W)$ 。

2.3 另一种思路

除上述思路外，完全背包问题还可从装入第 $i$ 种物品的数量出发。01背包问题中每种物品只能取0件或1件，而完全背包问题中可选取0件、1件、2件 $c d o t s$ 直到超过背包限重（ $k > j / w [i]$ ）。状态转移方程为：

# k为装入第i种物品的件数, k <= j/w[i]
dp[i][j] = max{(dp[i - 1][j - k * w[i]] + k * v[i]) for every k}

空间优化后，由于状态转移方程中的max项为 $d p [i - 1]$ ，与01背包问题相同， $j$ 必须逆向枚举。优化后的伪代码如下：

// 完全背包问题思路二伪代码(空间优化版)
dp[0...W] = 0
for i = 1...N
    for j = W...w[i] // 必须逆向枚举!!!
        for k = [0, 1... j/w[i]]
            dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i])

此方法在计算 $d p [i] [j]$ 时并非 $O (1)$ 时间复杂度，因此总的时间复杂度高于第一种思路，为 $O (N W W)$ 级别。

2.4 转化为01背包问题

由于01背包问题是最基本的背包问题，我们可以将完全背包问题转化为01背包问题求解。最简单的方法是将第 $i$ 种物品转化为 $W / w [i]$ 件费用和价值均不变的物品，然后求解01背包问题。更高效的转化方法是采用二进制思想，将第 $i$ 种物品拆分为重量为 $w_{i} i m e s 2^{k}$ 、价值为 $v_{i} i m e s 2^{k}$ 的若干件物品，其中 $k$ 取遍满足 $w_{i} i m e s 2^{k} l e q W$ 的非负整数。这样可将转换后的物品数量降为对数级别。具体代码见后续模板部分。

三、多重背包问题

3.1 问题描述

多重背包问题（bounded knapsack problem）与前面问题的不同之处在于，每种物品的数量是有限的。即一共有 $N$ 种物品，第 $i$ （ $i$ 从1开始）种物品的数量为 $n [i]$ ，重量为 $w [i]$ ，价值为 $v [i]$ 。在总重量不超过背包承载上限 $W$ 的情况下，求能够装入背包的物品的最大价值。

3.2 动态规划解法

与完全背包问题的第二种思路类似，从装入第 $i$ 种物品的数量出发，可装入0件、1件 $c d o t s$ $n [i]$ 件（同时需满足不超过背包限重）。状态转移方程为：

# k为装入第i种物品的件数, k <= min(n[i], j/w[i])
dp[i][j] = max{(dp[i - 1][j - k * w[i]] + k * v[i]) for every k}

空间优化后， $j$ 同样必须逆向枚举。优化后的伪代码如下：

// 多重背包问题伪代码(空间优化版)
dp[0...W] = 0
for i = 1...N
    for j = W...w[i] // 必须逆向枚举!!!
        for k = [0, 1... min(n[i], j/w[i])]
            dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i])

总的时间复杂度约为 $O (N W o v e r l i n e n) = O (W s u m_{i} n_{i})$ 级别。

3.3 转化为01背包问题

采用与完全背包问题类似的思路，可将多重背包问题转化为01背包问题。利用二进制思想将第 $i$ 种物品拆分为 $O (l o g n_{i})$ 件物品，将原问题转化为复杂度为 $O (W s u m_{i} l o g n_{i})$ 的01背包问题，相较于第一种分析方法有较大改进。具体代码见后续模板部分。

3.4 代码模板

以下是这三种背包问题的解题模板，方便实际解题时使用，尤其注意其中的二进制优化实现。

/*
https://tangshusen.me/2019/11/24/knapsack-problem/
01背包, 完全背包, 多重背包模板(二进制优化). 
2020.01.04 by tangshusen.

用法:
    对每个物品调用对应的函数即可, 例如多重背包:
    for(int i = 0; i < N; i++) 
        multiple_pack_step(dp, w[i], v[i], num[i], W);

参数:
    dp   : 空间优化后的一维dp数组, 即dp[i]表示最大承重为i的书包的结果
    w    : 这个物品的重量
    v    : 这个物品的价值
    n    : 这个物品的个数
    max_w: 书包的最大承重
*/
void zero_one_pack_step(vector<int>&dp, int w, int v, int max_w){
    for(int j = max_w; j >= w; j--) // 反向枚举!!!
        dp[j] = max(dp[j], dp[j - w] + v);
}

void complete_pack_step(vector<int>&dp, int w, int v, int max_w){
    for(int j = w; j <= max_w; j++) // 正向枚举!!!
        dp[j] = max(dp[j], dp[j - w] + v);

    // 法二: 转换成01背包, 二进制优化
    // int n = max_w / w, k = 1;
    // while(n > 0){
    //     zero_one_pack_step(dp, w*k, v*k, max_w);
    //     n -= k;
    //     k = k*2 > n ? n : k*2;
    // }
}

void multiple_pack_step(vector<int>&dp, int w, int v, int n, int max_w){
   if(n >= max_w / w) complete_pack_step(dp, w, v, max_w);
   else{ // 转换成01背包, 二进制优化
       int k = 1;
       while(n > 0){
           zero_one_pack_step(dp, w*k, v*k, max_w);
           n -= k;
           k = k*2 > n ? n : k*2;
       }
   }
}

四、背包问题的其他变种

4.1 恰好装满

在某些背包问题中，存在必须恰好装满背包的限制。此时，基本思路不变，但初始化时有所不同。若没有恰好装满的限制，可将 $d p$ 数组全部初始化为0，因为任何容量的背包都有一个合法解“什么都不装”，其价值为0。若有恰好装满的限制，则应将 $d p [0 d o t s N] [0]$ 初始化为0，其余 $d p$ 值初始化为 $- i n f t y$ ，因为只有容量为0的背包在不装任何物品时可被“恰好装满”，其他容量的背包初始时没有合法解。

4.2 求方案总数

除了求最大价值外，还有一类问题是求装满背包或将背包装至指定容量的方案总数。对于这类问题，只需将状态转移方程中的 max 操作改为 sum 操作，整体思路基本不变。例如，在完全背包问题中，转移方程变为：

dp[i][j] = sum(dp[i - 1][j], dp[i][j - w[i]]) // j >= w[i]

4.3 二维背包

前面讨论的背包问题的容量限制通常只有一个维度（如重量），而二维背包问题则有两个限制条件（如重量和体积）。选择物品时必须同时满足这两个条件。此类问题的解法与一维背包问题类似，只是 $d p$ 数组需要多开一维。例如，在5.4节的LeetCode题目中会有具体应用。

4.4 求最优方案

一般来说，背包问题主要求解最优值。若需要输出达到最优值的具体方案，可以参考动态规划问题输出方案的常规方法：记录每个状态的最优值是由哪种策略推导出来的，然后根据该策略回溯到上一个状态，依次向前推导。以01背包问题为例，我们可以使用另一个数组 $G [i] [j]$ 来记录方案。设 $G [i] [j] = 0$ 表示计算 $d p [i] [j]$ 时采用了max操作中的前一项（即 $d p [i - 1] [j]$ ）， $G [i] [j] = 1$ 表示采用了后一项。这分别代表了两种策略：未装入第 $i$ 个物品和装入了第 $i$ 个物品。实际上，我们也可以直接从已经计算好的 $d p [i] [j]$ 反推方案：若 $d p [i] [j] = d p [i - 1] [j]$ ，则说明未选择第 $i$ 个物品，反之则说明选择了。

五、LeetCode相关题目

5.1 Partition Equal Subset Sum（分割等和子集）

416. Partition Equal Subset Sum（分割等和子集）

题目给定一个只包含正整数的非空数组，要求判断是否可以将该数组分割成两个子集，使得两个子集的元素和相等。由于所有元素的和 $s u m$ 已知，若能分割，则两个子集的和都应为 $s u m / 2$ （因此 $s u m$ 不能为奇数）。该问题可转化为从数组中选取一些元素，使其和恰好为 $s u m / 2$ 。若将数组元素的值视为物品的重量，每件物品的价值均为1，则这是一个恰好装满的01背包问题。

我们定义空间优化后的状态数组 $d p$ ，由于是恰好装满，应将 $d p [0]$ 初始化为0，其余元素初始化为 $I N T_{M} I N$ ，然后按照类似1.2节的伪代码更新 $d p$ ：

int capacity = sum / 2;
vector<int>dp(capacity + 1, INT_MIN);
dp[0] = 0;
for(int i = 1; i <= n; i++)
    for(int j = capacity; j >= nums[i - 1]; j--)
        dp[j] = max(dp[j], 1 + dp[j - nums[i - 1]]);

更新完成后，若 $d p [s u m / 2] > 0$ ，则说明满足题意。

由于该题最终只需判断是否能进行划分，因此 $d p$ 数组的每个元素可定义为 bool 类型，将 $d p [0]$ 初始化为 true，其余元素初始化为 false，转移方程使用或操作。完整代码如下：

bool canPartition(vector<int>& nums) {
    int sum = 0, n = nums.size();
    for(int &num: nums) sum += num;
    if(sum % 2) return false;
    
    int capacity = sum / 2;
    vector<bool>dp(capacity + 1, false);
    dp[0] = true;
    for(int i = 1; i <= n; i++)
        for(int j = capacity; j >= nums[i - 1]; j--)
            dp[j] = dp[j] || dp[j - nums[i - 1]];
        
    return dp[capacity];
}

此外，该题还有一种更巧妙、更快的解法，基本思路是使用 bitset 记录所有可能子集的和，详见[我的Github](https://github.com/ShusenTang/LeetCode/blob/master/solutions/416. Partition Equal Subset Sum.md)。

5.2 Coin Change（零钱兑换）

322. Coin Change

题目给定一个目标金额 $a m o u n t$ 和一些硬币面值，假设每种面值的硬币数量无限，求最少需要多少个硬币才能组成目标金额。若将硬币面值视为物品重量，每个硬币的价值均为1，则该问题是一个恰好装满的完全背包问题。不过，这里求的是最少硬币数量，只需将2.2节的状态转移方程中的 max 操作改为 min 操作。由于是恰好装满，除 $d p [0]$ 外，其余元素应初始化为 $I N T_{M} A X$ 。完整代码如下：

int coinChange(vector<int>& coins, int amount) {
    vector<int>dp(amount + 1, INT_MAX);
    dp[0] = 0;
    
    for(int i = 1; i <= coins.size(); i++)
        for(int j = coins[i - 1]; j <= amount; j++){
            // 下行代码会在 1+INT_MAX 时溢出
            // dp[j] = min(dp[j], 1 + dp[j - coins[i - 1]]); 
            if(dp[j] - 1 > dp[j - coins[i - 1]])
                dp[j] = 1 + dp[j - coins[i - 1]];   
        }
    return dp[amount] == INT_MAX ? -1 : dp[amount];   
}

注意，1 + dp[j - coins[i - 1]] 可能会导致溢出，因此代码中采用了另一种写法。

此外，该题还可以通过搜索所有可能的组合并维护一个全局结果 $r e s$ 来求解，但直接搜索会超时，需要进行精心剪枝，剪枝后可击败99%的提交。详见[我的Github](https://github.com/ShusenTang/LeetCode/blob/master/solutions/322. Coin Change.md)。

5.3 Target Sum（目标和）

494. Target Sum

题目给定一个非负整数数组和一个目标值，要求给数组中的每个数字前添加正号或负号，使得组成的表达式结果等于目标值 $S$ ，求满足条件的组合数量。

假设所有元素的和为 $s u m$ ，添加正号的元素和为 $A$ ，添加负号的元素和为 $B$ ，则有 $s u m = A + B$ 且 $S = A - B$ ，解方程可得 $A = (s u m + S) / 2$ 。因此，问题转化为从数组中选取一些元素，使其和恰好为 $(s u m + S) / 2$ ，这是一个恰好装满的01背包问题，要求计算所有方案数。将1.2节状态转移方程中的 max 操作改为求和操作即可。需要注意的是，由于求的是方案数， $d p$ 数组应全部初始化为0，仅 $d p [0]$ 初始化为1。代码如下：

int findTargetSumWays(vector<int>& nums, int S) {
    int sum = 0;
    // for(int &num: nums) sum += num;
    sum = accumulate(nums.begin(), nums.end(), 0);
    if(S > sum || sum < -S) return 0; // 肯定不行
    if((S + sum) & 1) return 0; // 奇数
    int target = (S + sum) >> 1;
    
    vector<int>dp(target + 1, 0);
    
    dp[0] = 1;
    for(int i = 1; i <= nums.size(); i++)
        for(int j = target; j >= nums[i - 1]; j--)
            dp[j] = dp[j] + dp[j - nums[i - 1]];
    
    return dp[target];
}

5.4 Ones and Zeros（一和零）

474. Ones and Zeroes

题目给定一个仅包含0和1的字符串数组，要求从数组中选取尽可能多的字符串，使得这些字符串中包含的0和1的数量分别不超过 $m$ 和 $n$ 。

我们将每个字符串视为一个物品，字符串中0和1的数量分别视为两种“重量”，则该问题转化为一个二维01背包问题，背包的两个限重分别为 $m$ 和 $n$ ，要求背包能装下的物品的最大数量（可将每个物品的价值视为1）。

我们可以提前计算每个字符串的两个“重量” $w_{0}$ 和 $w_{1}$ 并存储在数组中，不过由于每个字符串的这两个值仅使用一次，因此可以在需要时直接计算。完整代码如下：

int findMaxForm(vector<string>& strs, int m, int n) {
    int num = strs.size();
    int w0, w1;
    
    vector<vector<int>>dp(m + 1, vector<int>(n + 1, 0));
    
    for(int i = 1; i <= num; i++){
        w0 = 0; w1 = 0;
        // 计算第i - 1个字符串的两个重量
        for(char &c: strs[i - 1]){
            if(c == '0') w0 += 1;
            else w1 += 1;
        }
        
        // 01背包, 逆向迭代更新dp
        for(int j = m; j >= w0; j--)
            for(int k = n; k >= w1; k--)
                dp[j][k] = max(dp[j][k], 1 + dp[j - w0][k - w1]);
    }
    
    return dp[m][n];
}