背包问题

0-1 背包
完全背包

给你一个背包, 它最多可以装载 capacity 的重量, 其中第 i 个物品的重量为 weights[i], 价值为 values[i]. 这个题目中的物品不可以分割, 要么装进包里, 要么不装, 不能说切成两块装一半, 这就是 0-1 背包的来历. 如以下示例, 最优是可以装载前两个物品, 它的总价值为 6.

首先明确状态跟选择, 显然状态是重量和价值, 而选择就是要么装要么不装.

接着明确 dp 数组的定义, 因为有两个状态, 所以 dp 是一个二维数组: 因此对于 dp[i][w] 的定义为: 对于前 i 个物品, 当前背包的容量为 w, 这种情况下可以装的最大价值是 dp[i][w].

比如说, 如果 dp[3][5] = 6, 其含义为: 对于给定的一系列物品中, 若只对前 3 个物品进行选择, 当背包容量为 5 时, 最多可以装下的价值为 6.

根据这个定义, 我们想求的最终答案就是 dp[N][W]. base case 就是 dp[0][..] = dp[..][0] = 0, 因为没有物品或者背包没有空间的时候, 能装的最大价值就是 0.

最后我们根据选择思考状态转移方程:

如果你不把第 i 个物品装到背包, 说明最大价值 dp[i][w] 应该等于 dp[i - 1][w], 即还是前一个状态
如果你把第 i 个物品装到背包, 那么 dp[i][w] 等于 dp[i - 1][w - weights[i - 1]] + weights[i - 1], 首先, 由于 i 是从 1 开始的, 所以对 weights 和 weights 的取值是 i - 1. 对于前半部分 dp[i - 1][w - weights[i - 1]], 就是说如果装了当前物品 i, 那么背包的剩余容量就变成了 w - weights[i - 1], 当然剩余容量可能超过了总容量, 后面会过滤掉这种情况; 对于后半部分 weights[i - 1], 就很显而易见了, 你把这个物品 i 装了进去, 那么就要把这个物品的价格加上嘛.

二维数组
一维数组

/**
 * @param {Number[]} weights 物品重量列表
 * @param {Number[]} values 物品价值列表
 * @param {Number} capacity 最多能装多少
 * @returns {Number}
 */
function knapsack2D(weights, values, capacity) {
  const n = weights.length
  const dp = Array(n + 1)
    .fill(null)
    .map(() => Array(capacity + 1).fill(0))

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (w < weights[i - 1]) {
        dp[i][w] = dp[i - 1][w]
      } else {
        dp[i][w] = Math.max(
          dp[i - 1][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1],
        )
      }
    }
  }
  return dp[n][capacity]
}

/**
 * @param {Number[]} weights 物品重量列表
 * @param {Number[]} values 物品价值列表
 * @param {Number} capacity 最多能装多少
 * @returns {Number}
 */
function knapsack1D(weights, values, capacity) {
  const n = weights.length
  const dp = Array(capacity + 1).fill(0)

  for (let i = 0; i < n; i++) {
    for (let w = capacity; w >= weights[i]; w--) {
      // 逆序遍历
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i])
    }
  }
  return dp[capacity]
}

Tips

求组合数: 外层 for 循环遍历物品, 内层 for 遍历背包.

求排列数: 外层 for 遍历背包, 内层 for 循环遍历物品.

在完全背包问题中, 每种物品都有无限多个, 可以选择多个相同的物品放入背包。目标仍然是将一些物品放入背包, 使得总价值最大, 且不超过背包的容量.

二维数组
一维数组

/**
 * @param {Number[]} weights 物品重量列表
 * @param {Number[]} values 物品价值列表
 * @param {Number} capacity 最多能装多少
 * @returns {Number}
 */
function completePack2D(weights, values, capacity) {
  const n = weights.length
  const dp = Array(n + 1)
    .fill(null)
    .map(() => Array(capacity + 1).fill(0))

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (w < weights[i - 1]) {
        dp[i][w] = dp[i - 1][w]
      } else {
        dp[i][w] = Math.max(
          dp[i - 1][w],
          dp[i][w - weights[i - 1]] + values[i - 1],
        )
      }
    }
  }
  return dp[n][capacity]
}

/**
 * @param {Number[]} weights 物品重量列表
 * @param {Number[]} values 物品价值列表
 * @param {Number} capacity 最多能装多少
 * @returns {Number}
 */
function completePack1D(weights, values, capacity) {
  const n = weights.length
  const dp = Array(capacity + 1).fill(0)

  for (let i = 0; i < n; i++) {
    for (let w = weights[i]; w <= capacity; w++) {
      // 正序遍历
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i])
    }
  }
  return dp[capacity]
}

题目汇总

题目	类型
416. 分割等和子集	0-1 背包
474. 一和零	0-1 背包
494. 目标和	0-1 背包
1049. 最后一块石头的重量-ii	0-1 背包
139. 单词拆分	完全背包(求排列数)
279. 完全平方数	完全背包
322. 零钱兑换	完全背包
377. 组合总和-iv	完全背包(求排列数)
518. 零钱兑换-ii	完全背包(求组合数)

题目汇总​

题目汇总