01 背包问题

每个物品有一定价值和容量，要么取要么不取，只能取一次

• 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
• 第 i 件物品的体积是 vi，价值是 wi。
• 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
• 输出最大价值。

输入：
N 件物品
V 容量
v[N] 体积
w[N] 价值

算法思路

01 背包是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

我们可以选择二维或一维解决 01 背包

二维解决 01 背包

$dp[i][j]$ 表示前 $i$ 种物品，体积为 $j$ 能放下的最大价值

状态转换表 TODO

一维解决 01 背包

dp[j]表示体积为 $j$ 能放下的最大价值

代码实现

function maxValue(N, V, v, w) {
  let dp = new Array(V + 1).fill(0);
  for (let i = 0; i < N; i++) {
    // 循环物品
    for (let j = V; j >= v[i]; j--) {
      // 循环体积；从大到小；
      dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
    }
  }
  return dp[V];
}

只用一维数组解 01 背包问题是十分必要的。我们最常使用的也是一维的方式。

总结

01 背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想， 另外，别的类型的背包问题往往也可以转换成 01 背包问题求解。