跳到主要内容

背包典型题

如何识别一道题能转成背包？​

  • 信号: 给定一组可选元素, 每个元素有"取或不取"的选择, 并对总量有约束;
  • 映射: 元素 → 物品; 元素的数值 → 重量/价值; 目标值 → 背包容量;
  • 目标决定变种: 可达性 → 存在背包; 方案数 → 组合背包; 最少个数 → 最值背包;

分割等和子集怎么转成存在背包？​

  • 问题: 判断能否把数组分成两个元素和相等的子集 (416);
  • 转化: 等价于从数组中选元素使和恰好等于 sum / 2;
  • 前置判断: sum 为奇数直接返回 false;
  • 模型: 0-1 背包 + 存在问题;
  • 状态: dp[i][j] 表示前 i 个元素能否凑出和 j;
  • 转移: dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]];
  • 初值: dp[i][0] = true, 其余为 false;
  • 答案: dp[n][sum/2];
const canPartition = (nums) => {
  const sum = nums.reduce((a, b) => a + b, 0);
  if (sum % 2 === 1) return false;
  const target = sum / 2;
  const dp = new 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];
};

目标和怎么转成组合背包？​

  • 问题: 给每个数字添加正号或负号, 求凑出 target 的方案数 (494);
  • 推导: 设正号元素和为 x, 则 x - (sum - x) = target, 得 x = (sum + target) / 2;
  • 合法性: sum + target 必须为偶数且非负, 否则方案数为 0;
  • 模型: 0-1 背包 + 组合问题, 容量为 x;
  • 初值: dp[0] = 1 (凑出 0 有一种方案: 全不选), 其余为 0;
  • 答案: dp[x];

零钱兑换如何同时体现恰好装满和不同目标？​

题目目标背包类型转移初值答案
322 最少硬币数最值完全背包min(dp[j], dp[j-v] + 1)dp[0] = 0, 其余 InfinityInfinity 则返回 -1
518 组合数计数完全背包dp[j] + dp[j-v]dp[0] = 1, 其余 0dp[amount]
const coinChange = (coins, amount) => {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (const coin of coins) {
    for (let j = coin; j <= amount; j++) dp[j] = Math.min(dp[j], dp[j - coin] + 1);
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
};

const change = (amount, coins) => {
  const dp = new 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];
};
  • 顺序要点: 两题都把硬币放在外循环, 得到的都是组合而非排列;
  • 复杂度: 均为时间 O(amount * coins.length), 空间 O(amount);