背包问题

发表于 更新于

还是挺常见的问题，感觉属于动态规划里的内容，但这部分东西也不少，而且很有规律，所以单独作为一篇

背包是啥

先介绍基础的背包问题，01背包，完全背包和多重背包。

1. 01背包

问题：有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 C i ，得到的价值是 W i 。求解将哪些物品装入背包可使价值总和最大。

每种物品只有选或不选两种情况，所以如果是暴力法时间复杂度也就是2^N，使用动态规划可以缩短至N * V。f[i][j]定义为前i个物品装入容量为j的背包的最大价值，f[i][j] = max(f[i - 1][j], f[i - 1][j - C[i]] + W[i])。

1
2
3
4
5
6
for (int i = 1; i <= N; i++) {
  	for (int j = C[i]; j <= V; j++) {
        if (j < C[i]) f[i][j] = f[i - 1][j];
      	else f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - C[i]] + W[i]);
    }
}

可以降维，但是 j 需要倒序循环，是为了不影响 j 之后的位置的计算。因为f[j] 的计算实际要用到 f[i-1][j] 和 f[i-1][j-C[i]]，就是上一次循环的f[j] 和 f[j-C[i]]，如果是正序f[j-C[i]] 在本次循环中就已经被改变了。

1
2
3
4
5
for (int i = 1; i <= N; i++) {
		for (int j = V; j >= C[i]; j--) {
        f[j] = Math.max(f[j], f[j - C[i]] + W[i]);
    }		
}

有很多DP可以转为这样的01背包问题，比如416题，可以转化为找到数组中是否存在和为target的子序列。

2. 完全背包

问题：有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品的费用是 C i ，价值是 W i 。求解：将哪些物品装入背包，可使这些物品的耗费的费用总 和不超过背包容量，且价值总和最大。

每种物品虽然是无限个，但不是就有无限种情况，因为有容量的限制，所以每个物品的情况有k种，满足k * Ci < V，f[i][j]定义和之前相同，f[i][j] = max(f[i - 1][j - k*C[i]] + k*W[i])。其实可以把完全背包转化为01背包，即每个物品的多次选择看作对多个物品的01选择，比如 i物品最多只能选择7个，那么可以看作有7个 i 物品，然后对其进行01选择：

1
2
3
4
5
6
7
for (int i = 1; i <= N; i++) {
  	for (int j = 0; j <= V; j++) {
      	for (int k = 0; k * C[i] <= j; k++) {
          	f[i][j] = Math.max(f[i][j], f[i - 1][j - k * C[i]] + k * W[i]);
        }
    }
}

完全背包有三重循环，但可以将其优化为二重循环，完全背包的特点恰是每种物品可选无限件，所以在考虑加选一件第 i 种物品这种策略时， 正需要一个可能已选入第 i 种物品的子结果f[i][j - C[i]]。所以状态转移方程可以转化为f[i][j] = max(f[i - 1][j], f[i][j - C[i]] + W[i])：

1
2
3
4
5
6
for (int i = 1; i <= N; i++) {
  	for (int j = 1; j <= V; j++) {
      	if (j < C[i]) f[i][j] = f[i - 1][j];
      	else f[i][j] = Math.max(f[i - 1][j], f[i][j - C[i]] + W[i]);  //这里使用f[i - 1][j]是因为需要不使用第i个物品的解，而 f[i][j - C[i]] 是包含了从 1 到 V / C[i] 这些情况，都使用了第 i 个物品。
    }
}

最后这个方程同样也可以降维。这里不改变 j 的遍历顺序，因为 01 背包中每次比较的都是上一轮的值，而完全背包中比较的一个是上一轮的，一个是本轮的：

1
2
3
4
5
for (int i = 1; i <= N; i++) {
  	for (int j = C[i]; j <= V; j++) {
      	f[j] = Math.max(f[j], f[j - C[i]] + W[i]);
    }
}

322题凑硬币就是很经典的完全背包问题。377也是，但是包含了组合的知识。

3. 多重背包

问题：有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 M i 件可用，每件耗费的空间是 C i ，价值是 W i 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

其实思路跟上面很像了，只是细节稍微不同，首先我们可以把多重背包转化为一个01背包问题，因为每个物品最多有M i 个选择，所以时间复杂度是 O(N * V * M)，这是可以解决问题的，但可以继续优化。即我们不用对每个物品从0到M i 都试一遍，可以将每个物品分成 log(M i) 份，比如说 第 i 个物品有13个，那么可以分为系数为1，2，4，6这4个物品，每个物品的值变为原来的1，2，4，6倍。这样时间复杂度可以降为 O(N * V * log(M))。

474题，相当于有两个限制条件的多重背包问题（基础的背包问题限制条件只有背包容量这一个）。

怎样解决

下面一些具体的问题解法

组合问题：

  1. 组合总和 Ⅳ
  2. 目标和
  3. 零钱兑换 II

True、False问题：

  1. 单词拆分
  2. 分割等和子集

最大最小问题：

  1. 一和零
  2. 零钱兑换

公式

  1. 组合问题公式

    dp[i] += dp[i-num]

  2. True、False问题公式

    dp[i] = dp[i] or dp[i-num]

  3. 最大最小问题公式

    dp[i] = min(dp[i], dp[i-num]+1) 或者 dp[i] = max(dp[i], dp[i-num]+1)

以上三组公式是解决对应问题的核心公式。

步骤：

  1. 分析是否为背包问题。
  2. 是以上三种背包问题中的哪一种。
  3. 是0-1背包问题还是完全背包问题。也就是题目给的nums数组中的元素是否可以重复使用。
  4. 如果是组合问题，是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法，不需要考虑顺序又有对应的解法。

接下来讲一下背包问题的判定
背包问题具备的特征：给定一个target，target可以是数字也可以是字符串，再给定一个数组nums，nums中装的可能是数字，也可能是字符串，问：能否使用nums中的元素做各种排列组合得到target。

背包问题技巧：
1.如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；

1
2
for num in nums:
    for i in range(target, nums-1, -1):

2.如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。

1
2
for num in nums:
    for i in range(nums, target+1):

3.如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。

1
2
for i in range(1, target+1):
    for num in nums: