Version: Next

完全背包问题

与 01 背包问题类似，只是每种物品的 数目无限

每种商品的上限与下限

  • 下限：一个都不拿
  • 上限：当前剩余容量 / 当前物品的重量 -> 最多可以拿这么多个

朴素完全背包解法

从 01 背包的代码修改得到完全背包的代码

  • 在 01 背包中，用 i 循环 dp 数组的行 （物品），j 循环 dp 数组的列 （背包容量）
  • 在 j 内部再添加一个循环 k，k 的取值范围为 0 ~ j/w[i]，表示对当前物品 i 拿 0、1、2、3...件
    • 相应的：减去的是 k 倍的重量 ，加上的是 k 倍的价值
01背包循环部分
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
完全背包添加k循环
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
for (int k = 1; k <= j / w[i]; k++) {
dp[j] = Math.max(dp[j], dp[j - k * w[i]] + k * v[i]);
}
}
}
  • 显然时间复杂度太高了

优化写法

手推打表

  • 01 背包打表
w 重量v 价值i\j012345678910
000000000000
21100111111111
33200133444444
45300135568899
7940013556991012
  • 完全背包打表
w 重量v 价值i\j012345678910
000000000000
21100112233445
33200133466799
45300135568101011
79400135569101012
  • (j / w[i]) * v[i]，无脑对着一个拿
    • 优化为在拿了 n 个当前物品 i 的基础上看能不能再来一个 i
    • dp[i][j - w[i]] +v[i]
  • dp[i - 1][j] 不拿当前物品，上一轮拿法的价值
优化完全背包
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
for (int k = 1; k <= j / w[i]; k++) {
dp[j] = Math.max(dp[j], dp[j - k * w[i]] + k * v[i]);
}
}
}
  • 01背包 -> dp[i - 1][j -w[i]] + v[i]
  • 完全背包 -> dp[i][j - w[i]] + v[i]

滚动数组压缩 + 同行递推

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

  • 和 01 背包压缩后的状态转移方程一模一样
  • 只是递推方向不同
  • 优化掉第三个 for 循环
完全背包滚动数组+同行递推
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (j >= w[i])
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
重要

二者的区别在于 递推方向

  • 01 背包 j 从后往前，因为它用的是上一行的旧数据
  • 完全背包 j 从前往后，因为它用的是当前行的新数据
  • 注意限制 j >= w[i]

再优化：j 从 w[i] 开始遍历，去除 if 判断

for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++) {
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}