背包问题

1. 01 背包问题
2. 完全背包问题
3. 多重背包问题
4. 混合背包问题
5. 二维费用的背包问题
6. 分组背包问题
7. 背包问题求方案数
8. 求背包问题的方案
9. 有依赖的背包问题

01 背包问题

有 n 件物品和一个容量是 v 的背包。每件物品仅有一件，第 i 件物品的重量是 weights[i]，价值是 values[i]。

求解将哪些物品装入背包，可使这些物品的总重量不超过背包容量，且总价值最大。

对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态只是 1 和 0，此问题称为 01 背包问题。

问题分析

假设：

• 物品个数 n = 5
• 物品重量 weights = [2, 2, 6, 5, 4]
• 物品价值 values = [6, 3, 5, 4, 6]
• 背包容量 W = 10

基本理解：

• 物品无法拆分成分数形式，如果能拆分，那就是属性贪婪算法问题
• 不一定恰好能装满背包
• 装满时总价值不一定最大
• 每样物品各一样
• 常规情况下，在表格中，价格和重量一般都是从上到下递增的。我们填表分析的时候，其实是事先默认了这种递增的关系

我们设置矩阵 f 来记录结果：

• j：从第四列开始到最后一列，表示背包的总容量，最大值为 10
• i：从第四列第二行开始到最后一行，下标从 0 开始，一共 5 个物品，所以 i 的最大值为 4。下面对应地我们用 i 表示物品的编号，i = 0 表示物品 0，i = 1 表示物品 1
• f[i][j]：表格中未填写的空格，表示背包内物品总价值，我们使用二维数组表示

接下来我们将从上到下，从左往右地填写这个表格。所以现在把注意力定位到 i = 0 和 j = 1 的空格上。

第一行分析

• 第一行：物品 i = 0 的体积为 2，价值为 6
  • i = 0 和 j = 0：背包容量为 0 时，什么也放不下，因此第一格只能填 0，程序表示为 f[0][0] = 0
  • i = 0 和 j = 1：当背包容量为 1 时，依然放不下 weights[0]，因此依然为 0，程序表示为 f[0][1] = 0
  • i = 0 和 j = 2：当背包容量为 2 时，能放下 weights[0]，于是有 f[0][2] = values[0] = 6
  • i = 0 和 j = 3：当背包容量为 3 时，也能放下 weights[0]，但是我们只有一个物品 0，因此它的价值依然是 6
  • i = 0 和 j = 4...10：于是当背包容量直到 10 为止，它的最大价值都是 values[0] = 6

根据第一行，我们得出以下方程式：

根据以上推导公式可得：当背包容量少于物品容积时，总价值为 0，否则为物品的价值。

第二行分析

然后我们看第二行，确定 f(1, 0)、f(1, 1)...f(1, 10) 这 11 个元素的值。

在这行可以由物品 0 和物品 1 进行自由组合，来装入背包。

• i = 1 和 j = 0：当背包容量为 0 时，依然什么也放不下，值为 0，但我们发觉它是上方格式的值一样的，f[1][0] = 0
• i = 1 和 j = 1：当背包容量为 1 时，依然什么也放不下，值为 0，但我们发觉它是上方格式的值一样的，f[1][1] = 0
• i = 1 和 j = 2：当背包容量为 2 时，它可以选择放入物品 1 或不放
  • 如果选择不放物品 1，背包里有物品 0，最大价值为 6
  • 如果选择放物品 1，我们要用算出背包放入物品 1 后还有多少容量，然后根据容量查出它的价值，再加上物品 1 的价值，即 f[0][j - w1] + v1

由于我们的目标是尽可能装最值钱的物品，因此放与不放，我们需要通过 比较 来决定，于是有以下推导公式：

显然物品 1 的价值 ，容量 ，因此这里填 。

• i = 1 和 j = 3：当背包容量为 3 时，情况相同
• i = 1 和 j = 4：当背包容量为 4 时，能同时放下物品 0 与物品 1，这个公式的计算也合乎我们的预期，得到 f[1][4] = 9
• i = 1 和 j > 4：当背包容量大于 4 时，由于背包只能放物品 0 与物品 1，那么它的最大价值也一直停留在

第三行分析

我们再看第三行：

• i = 2 和 j = 0：当背包容量为 0 时，什么都放不下，f[2][0] = 0
• i = 2 和 j = 1：当背包容量为 1 时，依然什么也放不下，f[2][1] = 0
• i = 2 和 j = 2：当背包容量为 2 时，虽然放不下 ，但我们根据上表得知这个容量时，背包能装下最大价值是 6
• 继续算下去，其实与上面推导的公式结果是一致的，说明公式是有效的
• i = 2 和 j = 8：当背包容量为 8 时，背包可以是放物品 0 和 1，或者放物品 1 和 2，或者放物品 0 和 2
  • 物品 0 和 1 的价值，我们在表中就可以看到是 9
  • 至于其他两种情况我们姑且不顾，我们目测就知道是最优值是 6 + 5 = 11，恰恰我们的公式也能正确计算出来
• i = 2 和 j = 10：当背包容量为 10 时，刚好三个物品都能装下，他们的总值为 f[2][10] = 14

整理第 1、2 行的适用方程：

稍微说明：假设前面的空已填好，例如 i = 2 和 j = 8。由上方数字可得，当前背包容量下，前面物品最大价值，那么在不考虑当前物品 2 的前提下，最小也有 9。若假设考虑物品 2，那么有添加物品 2 时，前面的物品分配剩余的背包容量，又由于横轴为背包容量，从上层对应剩余背包容量列可以找到最优解，那么当前行列最优解为两者之和。

根据此方程，继续计算下面各列，于是得到：

根据 0-1 背包问题的最优子结构性质，建立 的递归式：

代码实现

const knapsack = function (weights, values, W) {
  let f = [[]];

  // 先把第一行（i = 0）填满
  for (let j = 0; j <= W; j++) {
    if (j < weights[0]) {
      // 如果容量不能放下物品 0 的重量，那么价值为 0
      f[0][j] = 0;
    } else {
      // 否则等于物体 0 的价值
      f[0][j] = values[0];
    }
  }
  for (let j = 0; j <= W; j++) {
    // 从第二行（i = 1）开始
    for (let i = 1; i < weights.lngth - 1; i++) {
      if (!f[i]) {
        f[i] = [];
      }
      if (j < weights[i]) {
        // 背包容量小于当前比较物品质量
        f[i][j] = f[i - 1][j];
      } else {
        // 背包容量大于等于当前比较物品质量
        f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - weights[i]] + values[i]);
      }
    }
  }
  return f[weights.length - 1][W];
};

• 时间复杂度：O()
• 空间复杂度：O(n)

合并优化

合并循环

现在方法里面有两个大循环，它们可以合并成一个：

const knapsack = function (weights, values, W) {
  let f = new Array(weights.length);
  // 为每一行添加数组
  for (let i = 0; i < n; i++) {
    f[i] = [];
  }
  for (let i = 0; i < weights.length; i++) {
    for (let j = 0; j <= W; j++) {
      if (i === 0) {
        // 第一行
        f[i][j] = j < weights[i] ? 0 : values[i];
      } else {
        if (j < weights[i]) {
          // 等于之前的最优解
          f[i][j] = f[i - 1][j];
        } else {
          f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - weights[i]] + values[i]);
        }
      }
    }
  }

  return f[weights.length - 1][W];
};

添加第 -1 行，解决需要单独处理第一行的问题。因为 Math.max 可以轻松转换为三元表达式，结构极其相似。

const knapsack = function (weights, values, W) {
  // 数组定义：当背包容量为 i 时，装物品的最大价值
  let dp = new Array(weights.length);
  dp[-1] = new Array(W + 1).fill(0);

  // 外循环：对应第 i 件物品
  for (let i = 0; i < weights.length; i++) {
    // 注意边界，没有等号
    dp[i] = new Array(W).fill(0);

    // 内循环：容量
    for (let j = 0; j <= W; j++) {
      // 注意边界，有等号
      // 第 i 件商品重量是否大于背包容量 j 的情况
      if (j < weights[i]) {
        // 如果大于，那么背包可装载的最大价值应该是第 i-1 件商品在同等背包容量 j 的情况下可装载的最大价值
        // 当前物品，也就是第 i 件物品不装入背包
        dp[i][j] = dp[i - 1][j];
      } else {
        // 如果小于等于，那么背包可装载的最大价值应该是 [第 i-1 件商品在同等背包重量 j 的情况下可装载最大价值 ] 和 [第 i-1 件商品在背包当前背包容量 j - 当前第 i 件物品重量 + 当前第 i 件物品价值] 之间的最大值
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
      }
    }
  }

  return dp[weights.length - 1][W];
};

负一行的出现可以大大减少了在双层循环的分支判定。是一个很好的技巧。

完全背包问题

参考资料

• 📝 JavaScript 背包问题详解
• 📝 动态规划套路秒杀背包问题（2020-07-15）