01背包组合优化算法

引言

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

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

  1. 01背包问题
  2. 完全背包问题
  3. 多重背包问题

一、01背包问题

1.1 问题描述

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

1.2 动态规划解法

1.2.1 定义状态数组

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

1
dp[i][j]

1.2.2 状态转移方程

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

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

因此，状态转移方程为：

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

1.2.3 空间优化

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

1
2
3
4
5
// 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(NW)$，空间复杂度为 $O(W)$。由于 $W$ 的值是其位数的幂，所以该时间复杂度为伪多项式时间。

二、完全背包问题

2.1 问题描述

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

2.2 动态规划解法

2.2.1 定义状态数组

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

2.2.2 状态转移方程

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

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

状态转移方程为：

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

2.2.3 空间优化

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

1
2
3
4
5
// 完全背包问题思路一伪代码(空间优化版)
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(NW)$，空间复杂度为 $O(W)$。

2.3 另一种思路

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

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

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

1
2
3
4
5
6
// 完全背包问题思路二伪代码(空间优化版)
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])

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

2.4 转化为01背包问题

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

三、多重背包问题

3.1 问题描述

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

3.2 动态规划解法

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

1
2
# 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$ 同样必须逆向枚举。优化后的伪代码如下：

1
2
3
4
5
6
// 多重背包问题伪代码(空间优化版)
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(NWoverline{n}) = O(Wsum_{i}n_i)$ 级别。

3.3 转化为01背包问题

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

3.4 代码模板

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
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 恰好装满

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

4.2 求方案总数

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

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

4.3 二维背包

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

4.4 求最优方案

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

五、LeetCode相关题目

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

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

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

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

1
2
3
4
5
6
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]]);

更新完成后，若 $dp[sum / 2] > 0$，则说明满足题意。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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]] 可能会导致溢出，因此代码中采用了另一种写法。

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

5.3 Target Sum（目标和）

494. Target Sum

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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$ 并存储在数组中，不过由于每个字符串的这两个值仅使用一次，因此可以在需要时直接计算。完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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];
}