4.2.5 动态规划之背包问题

两个模型：0/1 背包和完全背包

0/1 背包

给定 N 个物品，其中第 i 个物品的体积是 Vi，价值是 Wi。有一个容积为 M 的背包，要求选择一些物品放入背包，使得在总体积不超过 M 的前提下，物品的价值总和最大。

朴素思路

依次考虑每个物品选还是不选——即子集问题，每个结点有 2 个分支，是个 2^n 指数级别的搜索。同时关注已经放入背包里的物品的总重量和总价值。“子集问题”详见《递归》部分。

动态规划

1. 重复子问题：opt[i][j] 表示从前 i 个物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和

   • 状态：物品 [i] 和总体积 [j]

   • 最优化目标：opt[i][j] 最大价值总和

2. 决策：对于第 i 个物品，可以做的决策是选或者不选

   • 当不选时，opt[i][j] = opt[i-1][j]

   • 当选择时，opt[i][j] = opt[i-1][j-Vi] + Wi

   • 而 opt[i][j] 的值就取以上两个中值最大的那个

     • 递推公式：opt[i][j] = max(opt[i-1][j], opt[i-1][j-Vi] + Wi)

3. 开始递推

   • 默认值：opt[i][j] = -Infinity

   • 起点：opt[0][0] = 0

   • 目标：max(...opt[N])

动态规划的核心代码：

// 最优化目标：opt[i][j] 表示从前 i 个物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和
let opt = new Array(N + 1); // (N+1)*(M+1)，多申请一个-当保护结点-以方便递推
for (let i = 0; i <= N; i++) opt[i] = new Array(M + 1).fill(-Infinity);
opt[0][0] = 0; // 递归起点

// 从小到大开始递推，先 for 状态，再 for 决策
for (let i = 1; i <= N; i++) { // [i] 物品
  for (let j = 0; j <= M; j++) { // [j] 总体积
    // 决策：选or不选
    opt[i][j] = opt[i - 1][j]; // 不选
    if (j >= V[i]) {
      opt[i][j] = Math.max(opt[i][j], opt[i - 1][j - V[i]] + W[i]); // 选
    }
  }
}

return Math.max(...opt[N]);

我们发现，状态 opt[i] 是先从 opt[i-1] 完全转移过来（当不选第 i 个物品时），然后是当 j >= V[i] 时，走“选择第 i 个物品”的决策。所以，在空间上，我们可以省略掉第一维的物品 [i] ，只留总体积 [j] 的维度。优化后的代码，如下：

// 最优化目标：opt[i][j] 表示从前 i 个物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和
let opt = new Array(M + 1).fill(-Infinity); // 省略了第一维，从 (N+1)*(M+1) 降低为 (M+1)
opt[0] = 0; // 递推起点

// 从小到大开始递推，先 for 状态，再 for 决策
for (let i = 1; i <= N; i++) { // [i] 物品
  // for (let j = V[i]; j <= M; j++) { // [j] 总体积
  for (let j = M; j >= V[i]; j--) { // 须倒序遍历 [j]，才能拿到之前二维时纯粹的 opt[i-1][j]
    opt[j] = Math.max(opt[j], opt[j - V[i]] + W[i]); // max(不选, 选)
  }
}

return Math.max(...opt);

代码的空间复杂度从 O(N*M) 降到了 O(M)。这就是 0/1 背包算法的通用代码，背包问题是一类特殊的动态规划问题。

看个例子感受下。

例 1：分割等和子集

题目：分割等和子集。给定一个只包含正整数的非空数组 nums，请判断是否可以将该数组分割成两个子集，使得两个子集的元素和相等。

这是一个子集问题：选一个子集，让它的元素之和等于原数组和的一半。

朴素思路

暴力搜素（枚举回溯）的代码实现，如下：

var canPartition = function(nums) {
  const n = nums.length;
  const sum = nums.reduce((a, b) => a + b);
  if (sum % 2 === 1) return false; // 若和是奇数，则直接返回false

  // 选择一个子集，使其元素之和等于target
  const target = sum / 2;
  let ans = false;

  // 子集问题，递归搜索：判断第pos个位置选or不选
  let seletedSum = 0; // 已选元素之和（状态空间-共享变量）
  const dfs = function(pos) {
    if (ans || seletedSum > target) return; // 剪枝
    if (seletedSum === target) { // 找到答案了
      ans = true;
      return;
    }
    if (pos === n) return; // 叶子结点（正常边界）

    // 本层逻辑：选or不选当前位置的数
    dfs(pos + 1); // 不选
    // 选
    seletedSum += nums[pos]; // 下探时+本层
    dfs(pos + 1);
    seletedSum -= nums[pos]; // 回溯时恢复现场
  };
  dfs(0); // 从位置 0 开始
  return ans;
};

执行结果：超出时间限制

0/1 背包

子集问题在有和限制的前提下，选数就和 0/1 背包一样。每个数就是一个物品，数的值就是物品的体积，此问题就是求：能否选出一些总体积等于 sum/2 的物品？

此时不用考虑“价值”（最优解问题），而是考虑“体积 M”是否可行（可行性问题）。

按照动态规划的思路进行分析，如下：

1. 重复子问题：opt[i][j] 表示从前 i 个数中选出一些数，总和是 j，是否可行？

   • 状态：数 [i] 和总和 [j]

   • 代表：opt[i][j] 是否可行

2. 决策：对于第 i 个数，可以选或者不选

   • 当不选时，opt[i][j] = opt[i-1][j]

   • 当选时，opt[i][j] = opt[i-1][j-nums[i]]

   • 而 opt[i][j] 的值就是这两个分支的逻辑或，即有一个分支是 true 则值就是 true

     • 递推公式：opt[i][j] = opt[i-1][j] || opt[i-1][j-nums[i]]

3. 开始递推

   • 默认值：opt[i][j] = false

   • 起点：opt[0][0] = true

   • 目标：opt[N][M] 是否可行

代码实现，如下：

var canPartition = function(nums) {
  const n = nums.length;
  const sum = nums.reduce((a, b) => a + b);
  if (sum % 2 === 1) return false; // 若和是奇数，则直接返回false

  // 选择一个子集，使其元素之和等于target
  const target = sum / 2;

  // opt[i][j] 表示从前 i 个数中选出一些数，总和是 j，是否可行？
  let opt = new Array(n + 1); // (N+1)*(M+1)，多申请一个-当保护结点-以方便递推
  for (let i = 0; i <= n; i++) opt[i] = new Array(target + 1).fill(false); // 初始值均为 false（不可达）
  opt[0][0] = true; // 递推起点

  // 从小到大开始递推，先 for 状态，再 for 决策
  for (let i = 1; i <= n; i++) { // [i] 物品-数字
    for (let j = 0; j <= target; j++) { // [j] 总体积-总和
      // 决策：选or不选，有一个分支是 true 就可以
      opt[i][j] = opt[i - 1][j]; // 不选
      if (j >= nums[i - 1]) {
        opt[i][j] = opt[i][j] || opt[i - 1][j - nums[i - 1]]; // 选
      }
    }
  }

  return opt[n][target]; // 直接返回目标状态是否可行
};

执行结果：通过

优化下代码的空间复杂度，将其从 O(nums.length*target) 降为 O(target)。如下：

var canPartition = function(nums) {
  const n = nums.length;
  const sum = nums.reduce((a, b) => a + b);
  if (sum % 2 === 1) return false; // 若和是奇数，则直接返回false

  // 选择一个子集，使其元素之和等于target
  const target = sum / 2;

  // opt[i][j] 表示从前 i 个数中选出一些数，总和是 j，是否可行？
  let opt = new Array(target + 1).fill(false);
  opt[0] = true;

  // 从小到大开始递推，先 for 状态，再 for 决策
  for (let num of nums) { // [i] 物品-数
    for (let j = target; j >= num; j--) { // [j] 总体积-总和，须倒序遍历，才能拿到之前二维时纯粹的 opt[i-1][j]
      opt[j] = opt[j] || opt[j - num]; // (不选, 选) 两个分支有一个是 true 就可以
    }
  }

  return opt[target];
};

执行结果：通过

完全背包

理论部分

与 0/1 背包相比，完全背包的物品不限个数。

完全背包：给定 N 种物品，其中第 i 种物品的体积是 Vi，价值是 Wi，并且每种物品都有无数个。有一个容积为 M 的背包，要求选择一些物品放入背包，使得在总体积不超过 M 的前提下，物品的价值总和最大。

完全背包的递推公式，和 0/1 背包的唯一不同就是：当从第 i 种物品中选择的时候是包含 i 的。

背包模型	递推公式 opt[i][j]
0/1 背包	max(opt[i-1][j], opt[i-1][j-Vi] + Wi) (不选第 i 个物品, 选择第 i 个物品)
完全背包	max(opt[i-1][j], opt[i][j-Vi] + Wi) (尚未选过第 i 种物品, 从第 i 种物品中选一个)

直接按照递推公式写，完全背包的代码如下：

// 最优化目标：opt[i][j] 表示从前 i 种物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和
let opt = new Array(N + 1); // (N+1)*(M+1)，多申请一个-当保护结点-以方便递推
for (let i = 0; i <= N; i++) opt[i] = new Array(M + 1).fill(-Infinity);
opt[0][0] = 0; // 递推起点

// 从小到大开始递推，先 for 状态，再 for 决策
for (let i = 1; i <= N; i++) { // [i] 物品
  for (let j = 0; j <= M; j++) { // [j] 总体积
    // 决策：选or不选
    opt[i][j] = opt[i - 1][j]; // 不选
    if (j >= V[i]) {
      opt[i][j] = Math.max(opt[i][j], opt[i][j - V[i]] + W[i]); // 选
    }
  }
}

return Math.max(...opt[N]);

优化下代码的空间复杂度，将其变为一维，如下：

// 最优化目标：opt[i][j] 表示从前 i 种物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和
let opt = new Array(M + 1); // 省略了第一维，从 (N+1)*(M+1) 降低为 (M+1)
opt[0] = 0; // 递推起点

// 从小到大开始递推，先 for 状态，再 for 决策
for (let i = 1; i <= N; i++) { // [i] 物品
  for (let j = V[i]; j <= M; j++) { // [j] 总体积，正序循环即可（便能重复选第 [i] 种物品了）
    opt[j] = Math.max(opt[j], opt[j - V[i]] + W[i]); // max(尚未选过, 选一个)
  }
}

return Math.max(...opt);

我们发现，把 0/1 背包算法中的状态 [j] 正序循环了之后，就变成完全背包算法了，因为这样就能很方便地实现重复选择第 i 种物品的逻辑了。

看两个例子感受下。

例 1：最少硬币个数

题目：零钱兑换的最少硬币个数。给定一个整数数组 coins（表示不同面额的硬币）和一个整数 amount（表示总金额），计算并返回可以凑成总金额的最少硬币个数。如果没有任何一种硬币组合能组成总金额，就返回 -1。假设每种硬币的数量是无限的。

零钱兑换的问题其实就符合完全背包模型。零钱=物品，面值=体积，价值=1，求最少兑换个数就是求价值的最小值。

用背包的思想来分析这个动态规划的问题，步骤如下：

1. 重复子问题：opt[i][j] 表示从前 i 种硬币中凑出总面额为 j 的最少硬币个数

   • 状态：硬币 [i] 和总面额 [j]

   • 最优化目标：opt[i][j] 最少硬币数

2. 决策：对于第 i 种硬币，可以选或者不选

   • 当不选时：opt[i][j] = opt[i-1][j]

   • 当选时：opt[i][j] = opt[i][j-coins[i]] + 1

   • 而 opt[i][j] 的值就取这两个分支的最小值

     • 递推公式：opt[i][j] = min(opt[i-1][j], opt[i][j-coins[i]] + 1)

3. 开始递推

   • 默认值：opt[i][j] = Infinity

   • 起点：opt[0][0] = 0

   • 目标：opt[N][amount]

直接套用递推公式，代码如下：

var coinChange = function(coins, amount) {
  const n = coins.length;
  // opt[i][j] 表示从前 i 种硬币中凑出总面额为 j 的最少硬币个数
  let opt = new Array(n + 1);
  for (let i = 0; i <= n; i++) opt[i] = new Array(amount + 1).fill(Infinity); // 默认值 Infinity
  opt[0][0] = 0; // 递推起点
  // 开始递推
  for (let i = 1; i <= n; i++) {
    const c = coins[i - 1];
    for (let j = 0; j <= amount; j++) {
      opt[i][j] = opt[i - 1][j];
      if (j >= c && opt[i][j - c] + 1 < opt[i][j]) {
        opt[i][j] = opt[i][j - c] + 1;
      }
    }
  }
  return opt[n][amount] === Infinity ? -1 : opt[n][amount];
};

执行结果：通过

优化下代码的空间复杂度，如下：

var coinChange = function(coins, amount) {
  // opt[i][j] 表示从前 i 种硬币中凑出总面额为 j 的最少硬币个数
  let opt = new Array(amount + 1).fill(Infinity);
  opt[0] = 0;
  for (let c of coins)
    for (let j = c; j <= amount; j++)
      opt[j] = Math.min(opt[j], opt[j - c] + 1);
  // 返回
  return opt[amount] === Infinity ? -1 : opt[amount];
};

执行结果：通过

例 2：硬币组合数

题目：零钱兑换的硬币组合数。给定一个整数数组 coins（表示不同面额的硬币）和一个整数 amount（表示总金额），计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0。假设每种面额的硬币有无限个。

这个问题是完全背包+计数。

1. 重复子问题：opt[i][j] 表示从前 i 种硬币中凑出总面额为 j 的硬币组合数

   • 状态：硬币 [i] 和总面额 [j]

   • 代表：opt[i][j] 硬币组合数

2. 决策：对于第 i 种硬币，有两种决策，选或者不选

   • 不选：opt[i][j] = opt[i-1][j]

   • 选：opt[i][j] = opt[i][j-coins[i]]

   • 而 opt[i][j] 的值等于它们之和

     • 递推公式：opt[i][j] = opt[i-1][j] + opt[i][j-coins[i]]

3. 开始递推

   • 默认值：opt[i][j] = 0

   • 起点：opt[i][0] = 1

   • 目标：opt[N][amount]

直接按递推公式写，代码如下：

var change = function(amount, coins) {
  const n = coins.length;
  // opt[i][j] 表示从前i种硬币中，能凑出总面额为j的硬币组合数
  let opt = new Array(n + 1);
  for (let i = 0; i <= n; i++) {
    opt[i] = new Array(amount + 1).fill(0); // 默认是 0
    opt[i][0] = 1; // 递推起点：[i][0] = 1
  }
  // 开始递推：不选+选
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= amount; j++) {
      opt[i][j] = opt[i - 1][j]; // 不选时
    }
    let c = coins[i - 1];
    for (let j = c; j <= amount; j++) {
      opt[i][j] += opt[i][j - c];
    }
  }
  return opt[n][amount];
};

执行结果：通过

优化下代码的空间复杂度，如下：

var change = function(amount, coins) {
  let opt = new Array(amount + 1).fill(0);
  opt[0] = 1;
  for (let c of coins)
    for (let j = c; j <= amount; j++)
      opt[j] += opt[j - c];
  return opt[amount];
};

执行结果：通过

总结

背包问题是一类特殊的动态规划问题，它就是在一定的体积限制下取物品，让价值最大化。背包有两个模型，分别是 0/1 背包和完全背包，它们的唯一区别就在于每种物品的个数是 1 个还是无限个。正因如此，它们的递推公式和通用代码之间的区别也不大。

递推公式的区别就在于：当从第 i 种物品中选择的时候是否包含 i。

背包模型	递推公式 opt[i][j]
0/1 背包	max(opt[i-1][j], opt[i-1][j-Vi] + Wi) (不选第 i 个物品, 选择第 i 个物品)
完全背包	max(opt[i-1][j], opt[i][j-Vi] + Wi) (尚未选过第 i 种物品, 从第 i 种物品中选一个)

通用代码中，倒序循环 [j] 时是 0/1 背包，正序循环时是完全背包。

// opt[i][j] 表示从前 i 种物品中选出了总体积为 j 的物品放入背包，物品的最大价值总和
let opt = new Array(M + 1).fill(-Infinity);
opt[0] = 0;
// 开始递推：先 for 状态，再 for 决策
for (let i = 1; i <= N; i++) {
  for (let j = M; j >= V[i]; j--) {
    // 倒序循环-0/1背包
    // for (let j = V[i]; j <= M; j++) { // 正序循环-完全背包
    opt[j] = Math.max(opt[j], opt[j - V[i]] + W[i]); // max(不选, 选)
  }
}
return Math.max(...opt);

背包问题就是“选或者不选”的子集问题，而子集问题适用于所有指数级别的搜索，所以背包的应用非常广泛，比如各种取物品且有体积限制的。它能求解最优解问题 min, max、可行性问题 |= boolean 以及计数问题 +=。