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 以及计数问题 +=

Last updated