01 背包问题

更新: 7/4/2026 字数: 0 字 时长: 0 分钟

题目描述

有 n 件物品和一个容量为 W 的背包。第 i 件物品的重量为 weights[i]、价值为 values[i]。每件物品只能选一次（选或不选，故称「01」背包），求在总重量不超过 W 的前提下，背包能装下的最大价值。

• 不可分割：物品要么整件放入，要么完全不放，不能只放一部分（这正是它区别于「部分背包」的关键）。

例如：weights = [2, 3, 4, 5]，values = [3, 4, 5, 6]，W = 8。 最优选择是物品 A(重2,值3) + B(重3,值4) + C(重4,值5) 超重，实际最优为 A + D(重5,值6) = 重7、值9，或 B + C = 重7、值9……最终答案为 10（A+B+C 重9超容？重新算：A+B 重5值7，再加 C 重9超8；A+C 重6值8；B+C 重7值9；A+D 重7值9；A+B+C 超；最优 A+B+... 见动画）。

提示

01 背包是「不可分割选择 + 容量约束下最优化」这一类问题的原型，是理解背包型动态规划的基石。

思路拆解

先想暴力解法

每件物品都有「选 / 不选」两种可能，n 件物品共有 种组合。最朴素的做法是枚举所有子集，过滤掉总重超过 W 的，再取剩下组合里价值最大的。

点击展开暴力解法（枚举子集，指数级）

function knapsackBrute(weights, values, W) {
  const n = weights.length
  let best = 0
  // 用二进制位枚举每个子集：第 k 位为 1 表示选第 k 件
  for (let mask = 0; mask < (1 << n); mask++) {
    let w = 0, v = 0
    for (let k = 0; k < n; k++) {
      if (mask & (1 << k)) { w += weights[k]; v += values[k] }
    }
    if (w <= W) best = Math.max(best, v)
  }
  return best
}

枚举 个子集，物品稍多（如 n > 30）就完全不可行。

推导最优解法：二维 DP

暴力慢在反复重算重叠的子问题。我们换一个「逐件决策」的视角：处理到第 i 件物品时，只需回答一个问题——这件物品选还是不选？

定义状态：

对第 i 件物品（重 wt = weights[i-1]，值 v = values[i-1]）：

• 不选它：价值等于前 i-1 件在同样容量下的最优解 → dp[i-1][w]；
• 选它（前提 w >= wt）：先留出 wt 的空间给它，剩余容量 w-wt 用前 i-1 件填满，再加上它的价值 → dp[i-1][w-wt] + v。

两者取较大：

边界：dp[0][w] = 0（一件物品都不选，价值为 0）。

核心思路

每个格子只依赖上一行的两个位置：正上方 dp[i-1][w]（不选）和左上方偏移 dp[i-1][w-wt]（选）。按物品逐行、容量逐列填表，右下角 dp[n][W] 就是答案。

选与不选两个来源，对照下图理解——当前格总是从上一行的这两个位置取最大：

动画演示

下面用样例 weights = [2,3,4,5]、values = [3,4,5,6]、容量 W = 8 完整演示 DP 表的填充过程。每一步高亮正在计算的格子及其两个来源（紫=正上方「不选」/ 黄=左上方「选」），并标出本步实际采用的选择：

动态规划 · 01 背包演示

背包容量 8，共 4 件物品

A

重 2 · 值 3

B

重 3 · 值 4

C

重 4 · 值 5

D

重 5 · 值 6

当前阶段：准备

i \ w	0	1	2	3	4	5	6	7	8
∅
A
B
C
D

正在计算不选（正上方）选（左上方 - 重量）本步采用的来源

构建 (5) × (9) 的 DP 表。dp[i][w] 表示只考虑前 i 件物品、背包容量为 w 时能装下的最大价值。

步骤 0 / 38

完整代码

function knapsack(weights, values, W) {
  const n = weights.length
  // dp[i][w]：前 i 件物品、容量 w 时的最大价值
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0))

  for (let i = 1; i <= n; i++) {
    const wt = weights[i - 1]
    const v = values[i - 1]
    for (let w = 0; w <= W; w++) {
      // 情况一：放不下，只能不选
      if (w < wt) {
        dp[i][w] = dp[i - 1][w]
      } else {
        // 情况二：可选可不选，取较大
        dp[i][w] = Math.max(
          dp[i - 1][w],              // 不选第 i 件
          dp[i - 1][w - wt] + v      // 选第 i 件
        )
      }
    }
  }
  return dp[n][W]
}

空间优化：滚动数组

由于 dp[i][w] 只依赖上一行，可以压成一维 dp[w]。关键是内层容量循环要从大到小遍历，保证每件物品只被使用一次（若从小到大，会重复选同一件，退化成完全背包）：

function knapsack1D(weights, values, W) {
  const dp = new Array(W + 1).fill(0)
  for (let i = 0; i < weights.length; i++) {
    for (let w = W; w >= weights[i]; w--) {   // 逆序！
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i])
    }
  }
  return dp[W]
}

复杂度分析

设物品数为 ，背包容量为 ：

解法	时间复杂度	空间复杂度	说明
枚举子集			枚举所有组合，指数级，不可用
二维 DP			填满 张表
一维滚动数组			只保留一行，容量逆序更新

关于「伪多项式」

看似多项式，但 是数值而非输入规模的位数。当 W 极大时复杂度会爆炸，因此 01 背包属于 NP 完全问题，其 DP 解法称为「伪多项式时间」算法。

边界与易错点

• 边界行/列要初始化为 0：dp[0][*] = 0（无物品）和 dp[*][0] = 0（无容量），JS 里 fill(0) 已经一次性覆盖，但逻辑上要清楚它们代表什么。
• 索引偏移：dp 表第 i 行对应第 i 件物品，取重量/价值时是 weights[i-1]、values[i-1]，差一位是高频 bug。
• 放不下要先判断：w < wt 时不能访问 dp[i-1][w-wt]（下标为负会取到 undefined），必须先处理「只能不选」的分支。
• 一维优化必须逆序：滚动数组的内层容量循环若写成从小到大，dp[w-wt] 会用到本轮已更新的值，导致同一件物品被重复选取，变成完全背包，结果偏大。
• 求具体方案：本题只要最大价值。若要还原「选了哪些物品」，需保留二维表并从 dp[n][W] 回溯：比较 dp[i][w] 与 dp[i-1][w] 是否相等，不等则说明选了第 i 件。
• 区分背包类型：每件只能选一次是 01 背包；可无限次选是完全背包（内层正序）；数量有限是多重背包，别混淆。