背包问题

讲解

背包问题是 DP 里最成体系的一族：给定一组物品（各有重量和价值）和容量有限的背包，求最大价值或可行性。它的地位相当于 DP 的「普通话」——大量题目（分割等和子集、零钱兑换、目标和）都是背包的换装。学会背包的通用建模，等于解锁了一整片题型。

0-1 背包（每件物品最多选一次）的状态定义：dp[i][c] = 前 i 件物品、容量 c 下的最大价值；转移是经典的「选或不选」：dp[i][c] = max(dp[i-1][c], dp[i-1][c-w] + v)。工程上压成一维滚动数组，但有一个性命攸关的细节：容量必须倒序遍历——正序的话同一件物品会在同一轮里被重复取用，0-1 背包就悄悄变成了完全背包。完全背包（每件无限取）恰好反过来：容量正序遍历。这一反一正是背包问题最著名的考点，理解它靠的是「转移来源是同层还是上一层」：倒序时 dp[c-w] 还是上一轮的值（没选过本物品），正序时已是本轮更新过的值（可以再次用本物品）。

识别背包换装题的能力比默写模板值钱。分割等和子集：问能否选出若干数和为总和的一半——物品是数字、重量和价值都是数值本身、容量是 sum/2 的 0-1 可行性背包。零钱兑换（最少硬币数）：硬币无限用、求凑满 amount 的最少件数——容量正序的完全背包，目标从 max 价值换成 min 件数，初始化从 0 换成 Infinity。套路：先问「物品是什么、能不能重复选」，再问「求最大价值、可行性还是方案数/最小用量」，答案就落回模板。

示例

0-1 背包（倒序）、完全背包（正序）、分割等和子集（可行性背包）、零钱兑换（最少硬币）：

import assert from 'node:assert/strict';

// 0-1 背包：容量倒序，保证每件物品最多取一次
function knapsack01(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let c = capacity; c >= weights[i]; c--) {
      dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

// 完全背包：容量正序，同件物品可重复取用
function knapsackComplete(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let c = weights[i]; c <= capacity; c++) {
      dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

// 分割等和子集：容量 sum/2 的 0-1 可行性背包
function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const x of nums) {
    for (let c = target; c >= x; c--) {
      dp[c] = dp[c] || dp[c - x];
    }
  }
  return dp[target];
}

// 零钱兑换：完全背包求最少件数，不可达用 Infinity 占位
function coinChange(coins, amount) {
  const INF = amount + 1; // 超过任何合法答案的大数
  const dp = new Array(amount + 1).fill(INF);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (a >= coin) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
}

assert.strictEqual(knapsack01([2, 3, 4, 5], [3, 4, 5, 6], 5), 7); // 物品 2+3 -> 价值 3+4
assert.strictEqual(knapsackComplete([2, 3, 4], [3, 4, 5], 5), 7); // 2+3 各取一件

assert.strictEqual(canPartition([1, 5, 11, 5]), true); // [1,5,5] 与 [11]
assert.strictEqual(canPartition([1, 2, 3, 5]), false); // 总和为奇数

assert.strictEqual(coinChange([1, 2, 5], 11), 3); // 5+5+1
assert.strictEqual(coinChange([2], 3), -1);

console.log('背包示例全部通过');

对比 knapsack01 与 knapsackComplete：两段代码只差容量循环的方向。试着把 knapsack01 改成正序再跑断言——结果会变大（物品被重复取），这个「错误实验」能让你一辈子记住遍历方向的分量。

常见坑

• 0-1 背包容量正序遍历：同一件物品被取多次，答案偏大——背包第一坑，遇到先检查循环方向。
• 完全背包求方案数时物品和容量循环嵌套顺序错：求「组合数」（不考虑顺序）要物品在外、容量在内；容量在外算出来的是「排列数」，会多算。
• 求最小用量时初始化成 0：最小值问题的不可达状态要初始化为 Infinity（或答案上界 + 1），否则不可达被当成 0 参与 min 计算。
• 可行性背包忘记容量倒序：canPartition 也是 0-1 背包，正序会让一个数被用多次，答案错成真。
• 奇数总和还硬跑 DP：分割等和子集先判 total % 2，奇数直接 false——先排除平凡情形是背包题的第一步。

小结

背包 = 「选或不选 / 选几次」的 DP；0-1 容量倒序、完全背包正序；换装题先识别物品与目标类型（最大价值 / 可行性 / 最小用量）。下一章看 DP 的对照思想：贪心算法。