背包问题 (Knapsack Problem)

[!abstract] 核心思想将每件物品选择与否转化为状态，利用 dp 数组存储子问题最优解。

问题分类

类型	每件物品	背包容量	复杂度
0/1背包	选 0 或 1 次	有限	O(n×W)
完全背包	无限次	有限	O(n×W)
多重背包	k_i 次	有限	O(n×W×k)
分组背包	每组选 1 件	有限	O(n×W)

1. 0/1 背包

问题

n 件物品，每件重量 w[i]，价值 v[i]
容量为 W 的背包
每件物品只能选一次，最大价值？

解法

typescript

function knapsack01(weights: number[], values: number[], W: number): number {
  const n = weights.length;
  // dp[i][j] = 前 i 件物品，容量为 j 时的最大价值
  const dp: number[][] = Array.from({ length: n + 1 }, () =>
    Array(W + 1).fill(0)
  );

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= W; j++) {
      // 不选第 i 件
      dp[i][j] = dp[i - 1][j];

      // 选第 i 件（如果能装下）
      if (j >= weights[i - 1]) {
        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
      }
    }
  }

  return dp[n][W];
}

// ✅ 空间优化 - 一维数组
function knapsack01Optimized(weights: number[], values: number[], W: number): number {
  const dp = Array(W + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    // 倒序遍历保证每件物品只选一次
    for (let j = W; j >= weights[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }

  return dp[W];
}

图解

容量 j:  0  1  2  3  4  5
物品 0:  0  0  0  0  0  0
物品 1:  0  X  X  X  X  X  ← 选
物品 2:  0  X  X  X  X  X  ← ...

空间优化关键

0/1 背包: j 倒序遍历
完全背包: j 正序遍历

2. 完全背包

问题

每件物品有无限件可选

解法

typescript

function completeKnapsack(weights: number[], values: number[], W: number): number {
  const dp = Array(W + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    // 正序遍历 - 每件物品可重复选
    for (let j = weights[i]; j <= W; j++) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }

  return dp[W];
}

0/1 vs 完全背包对比

特征	0/1 背包	完全背包
遍历顺序	`j = W → weights[i]`	`j = weights[i] → W`
每件物品	选 0/1 次	选任意次

3. 多重背包

问题

每件物品最多选 k_i 次

解法

typescript

function multipleKnapsack(weights: number[], values: number[], counts: number[], W: number): number {
  const dp = Array(W + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    // 枚举选择次数
    for (let j = W; j >= 0; j--) {
      for (let k = 1; k <= counts[i] && k * weights[i] <= j; k++) {
        dp[j] = Math.max(dp[j], dp[j - k * weights[i]] + k * values[i]);
      }
    }
  }

  return dp[W];
}

优化：二进制拆分

typescript

// 将 k 拆分为 1,2,4,8,... 转为 0/1 背包
function binaryMultipleKnapsack(weights: number[], values: number[], counts: number[], W: number): number {
  const dp = Array(W + 1).fill(0);
  const newWeights: number[] = [];
  const newValues: number[] = [];

  // 二进制拆分
  for (let i = 0; i < weights.length; i++) {
    let k = 1;
    while (k <= counts[i]) {
      newWeights.push(weights[i] * k);
      newValues.push(values[i] * k);
      counts[i] -= k;
      k *= 2;
    }
    if (counts[i] > 0) {
      newWeights.push(weights[i] * counts[i]);
      newValues.push(values[i] * counts[i]);
    }
  }

  // 0/1 背包
  for (let i = 0; i < newWeights.length; i++) {
    for (let j = W; j >= newWeights[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - newWeights[i]] + newValues[i]);
    }
  }

  return dp[W];
}

4. 分组背包

问题

n 组，每组至多选一件，容量 W

typescript

function groupKnapsack(groupItems: number[][][], values: number[][], W: number): number {
  const dp = Array(W + 1).fill(0);

  for (let g = 0; g < groupItems.length; g++) {
    for (let j = W; j >= 0; j--) {
      for (let k = 0; k < groupItems[g].length; k++) {
        const [weight, value] = groupItems[g][k];
        if (j >= weight) {
          dp[j] = Math.max(dp[j], dp[j - weight] + value);
        }
      }
    }
  }

  return dp[W];
}

5. 二维费用背包

问题

每件物品有两个维度的消耗（如重量和体积）
同时满足两个约束的最大价值

typescript

function twoDimensionKnapsack(
  weights: number[],
  volumes: number[],
  values: number[],
  W: number,   // 最大重量
  V: number    // 最大体积
): number {
  const dp: number[][] = Array.from({ length: W + 1 }, () =>
    Array(V + 1).fill(0)
  );

  for (let i = 0; i < weights.length; i++) {
    for (let j = W; j >= weights[i]; j--) {
      for (let k = V; k >= volumes[i]; k--) {
        dp[j][k] = Math.max(dp[j][k], dp[j - weights[i]][k - volumes[i]] + values[i]);
      }
    }
  }

  return dp[W][V];
}

经典应用

题目	两个维度
一和零	0的数量，1的数量
旅行商问题	访问状态，当前城市

6. 背包问题变体详解

变体1: 分割等和子集

问题: 能否将数组分成两个和相等的子集？

typescript

function canPartition(nums: number[]): boolean {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2 !== 0) return false;

  const target = sum / 2;
  const dp = Array(target + 1).fill(false);
  dp[0] = true;

  for (const num of nums) {
    // 倒序遍历
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }

  return dp[target];
}

为什么是 0/1 背包？

等价转换:
- 目标和 = sum/2
- 从数组中选若干数，和为 sum/2
- 等价于: 选一个子集，和为 target

物品: 每个数字
重量: 数字本身
价值: 数字本身
容量: target

问: 能否装满背包?

变体2: 目标和

问题: 在数字间添加 +/-，使得结果等于 target

typescript

function findTargetSumWays(nums: number[], target: number): number {
  const sum = nums.reduce((a, b) => a + b, 0);

  // 转换: 正数集合P，负数集合N
  // sum(P) - sum(N) = target
  // sum(P) + sum(N) = sum
  // 2 * sum(P) = sum + target
  // sum(P) = (sum + target) / 2

  if (Math.abs(target) > sum) return 0;
  if ((sum + target) % 2 !== 0) return 0;

  const newTarget = (sum + target) / 2;
  const dp = Array(newTarget + 1).fill(0);
  dp[0] = 1;

  for (const num of nums) {
    for (let j = newTarget; j >= num; j--) {
      dp[j] += dp[j - num];
    }
  }

  return dp[newTarget];
}

数学转换图解

原问题: +1 -2 +3 -4 = -2
         ↓
等价变换:
正数集合 P = {1, 3} → sum = 4
负数集合 N = {2, 4} → sum = 6

sum(P) - sum(N) = target
sum(P) - (sum - sum(P)) = target
2 * sum(P) = sum + target
sum(P) = (sum + target) / 2

问题变成: 从数组选若干数，和为 (sum+target)/2

变体3: 完全平方数（最小数量）

typescript

function numSquares(n: number): number {
  // 完全背包: 最少几个完全平方数加起来等于 n
  const dp = Array(n + 1).fill(Infinity);
  dp[0] = 0;

  // 物品: 1, 4, 9, 16, ...
  for (let i = 1; i * i <= n; i++) {
    for (let j = i * i; j <= n; j++) {
      dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
    }
  }

  return dp[n];
}

变体4: 零钱兑换 II（组合数）

typescript

function change(amount: number, coins: number[]): number {
  const dp = Array(amount + 1).fill(0);
  dp[0] = 1;

  // 外层循环物品，内层循环金额
  // 保证顺序固定 → 组合数（不重复计数排列）
  for (const coin of coins) {
    for (let j = coin; j <= amount; j++) {
      dp[j] += dp[j - coin];
    }
  }

  return dp[amount];
}

// ⚠️ 注意: 如果外层循环金额，内层循环物品 → 排列数
// dp[j] = sum(dp[j - coin]) for coin in coins

组合 vs 排列

coins = [1, 2], amount = 3

组合数（外层物品）:
  先用1: 1,1,1 / 1,2
  先用2: 2,1
  去重后: {1,1,1}, {1,2}, {2,1}? 
  实际: {1,1,1}, {1,2} (外层物品保证了不同顺序不会重复)

排列数（外层金额）:
  dp[3] = dp[2] + dp[1]
        = {1,1} + {1} / {2} + {1}
        = {1,1,1}, {1,2}, {2,1}

7. 背包问题总结

模板速查表

类型	核心特征	遍历顺序	状态转移
0/1背包	每件选一次	物品→容量(倒序)	`dp[j] = max(dp[j], dp[j-w]+v)`
完全背包	每件无限	物品→容量(正序)	`dp[j] = max(dp[j], dp[j-w]+v)`
多重背包	每件k次	物品→容量→次数	枚举次数或二进制拆分
分组背包	每组选一件	组→容量→组内	枚举组内物品
二维背包	两个约束	物品→容量1→容量2	`dp[j][k] = max(...)`

通用代码模板

typescript

// 0/1 背包
for (let i = 0; i < n; i++) {
  for (let j = W; j >= weights[i]; j--) {
    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
  }
}

// 完全背包
for (let i = 0; i < n; i++) {
  for (let j = weights[i]; j <= W; j++) {
    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
  }
}

// 组合数（先物品后容量）
// 排列数（先容量后物品）

经典例题

题目	类型	特点
分割等和子集	0/1背包	价值=重量
目标和	0/1背包	加减法转换
完全平方数	完全背包	找最少完全平方数
零钱兑换 II	完全背包	组合数
一和零	二维背包	两个约束
单词拆分	完全背包	字符串组合

参见: **DP算法索引**

背包问题 (Knapsack Problem) ​

问题分类 ​

1. 0/1 背包 ​

问题 ​

解法 ​

图解 ​

2. 完全背包 ​

问题 ​

解法 ​

0/1 vs 完全背包对比 ​

3. 多重背包 ​

问题 ​

解法 ​

优化：二进制拆分 ​

4. 分组背包 ​

问题 ​

5. 二维费用背包 ​

问题 ​

经典应用 ​

6. 背包问题变体详解 ​

变体1: 分割等和子集 ​

为什么是 0/1 背包？ ​

变体2: 目标和 ​

数学转换图解 ​

变体3: 完全平方数（最小数量） ​

变体4: 零钱兑换 II（组合数） ​

组合 vs 排列 ​

7. 背包问题总结 ​

模板速查表 ​

通用代码模板 ​

经典例题 ​

背包问题 (Knapsack Problem)

问题分类

1. 0/1 背包

问题

解法

图解

2. 完全背包

问题

解法

0/1 vs 完全背包对比

3. 多重背包

问题

解法

优化：二进制拆分

4. 分组背包

问题

5. 二维费用背包

问题

经典应用

6. 背包问题变体详解

变体1: 分割等和子集

为什么是 0/1 背包？

变体2: 目标和

数学转换图解

变体3: 完全平方数（最小数量）

变体4: 零钱兑换 II（组合数）

组合 vs 排列

7. 背包问题总结

模板速查表

通用代码模板

经典例题