背包问题

0-1 背包

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

W = 4
N = 3
wt = [2, 1, 3]
val = [4, 2, 3]

解决思路

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

接着明确 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 - wt[i - 1]] + val[i - 1], 首先, 由于 i 是从 1 开始的, 所以对 val 和 wt 的取值是 i - 1. 对于前半部分 dp[i - 1][w-wt[i - 1]], 就是说如果装了当前物品 i, 那么背包的剩余容量就变成了 w-wt[i - 1], 当然剩余容量可能超过了总容量, 后面会过滤掉这种情况; 对于后半部分 val[i - 1], 就很显而易见了, 你把这个物品 i 装了进去, 那么就要把这个物品的价格加上嘛.

/**
 * @param {Number} W 背包能装多少重量
 * @param {Number} N 背包能装多少个商品
 * @param {Number[]} wt 物品重量列表
 * @param {Number[]} val 物品价值列表
 * @returns {Number}
 */
export function knapsack(
  W: number,
  N: number,
  wt: number[],
  val: number[],
): Number {
  const dp: number[][] = new Array(N + 1)
    .fill(0)
    .map(() => new Array(W + 1).fill(0))

  for (let i = 1; i <= N; i++) {
    for (let w = 1; w <= W; w++) {
      if (w - wt[i - 1] < 0) {
        // 当前背包容量装不下,只能选择不装入背包
        dp[i][w] = dp[i - 1][w]
      } else {
        // 装入或者不装入背包, 择优
        dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1])
      }
    }
  }

  return dp[N][W]
}

题目汇总

题目	类型
416. 分割等和子集	0-1 背包
474. 一和零	0-1 背包
494. 目标和	0-1 背包
322. 零钱兑换	完全背包
518. 零钱兑换-ii	背包组合