背包变种

背包变种主要变哪几处？

• 模型不变: 状态仍是"前 i 件物品、容量 c";
• 三处可替换:
  • 目标运算: 取最值 max/min、计数求和、布尔或 ||;
  • 初值: 由问题目标决定, 不再是统一的全 0;
  • 循环边界: 第二层容量从 0 还是 1 开始;
• 对照基础写法见 0-1 背包 与 完全背包;

求最值、组合、存在三类问题的转移如何改？

类型	目标	0-1 背包转移	完全背包转移
最值	最大/最小价值	max(dp[i-1][c], dp[i-1][c-w] + v)	max(dp[i-1][c], dp[i][c-w] + v)
组合	方案数	dp[i-1][c] + dp[i-1][c-w]	dp[i-1][c] + dp[i][c-w]
存在	是否可行	dp[i-1][c] || dp[i-1][c-w]	dp[i-1][c] || dp[i][c-w]

• 统一规律: 把"选入后的结果"从"取最大值"换成"相加"或"逻辑或";
• 最值中的 v 可以是物品价值 val[i-1], 也可以是常数 1 (求最少件数);

第二层循环的起点该取 0 还是 1？

• 判断依据: dp[0][i] (i != 0) 在转移过程中是否恒定不变;
• 最值问题与存在问题: 这些初值不参与更新, 容量从 1 开始即可;
• 组合问题: dp[0][c] 可能被更新, 容量必须从 0 开始;
• 例: 零钱兑换 2 的 dp[i][0] = 1 在组合计数中会被反复引用;

恰好装满背包时初值怎么改？

• 语义: 只有"容量恰好用尽"才算合法状态, 其它容量视为不可达;
• 最值问题:
  • dp[i][0] = 0 (容量为 0 必然装满);
  • 其余初值按问题取 -Infinity (求最大) 或 Infinity (求最小);
• 组合问题: dp[i][0] = 1, 其余为 0;
• 存在问题: dp[i][0] = true, 其余为 false;
• 对照: 非恰好装满的背包问题, 初值全部为 0/1/false 的中性值;

恰好装满时答案怎么返回？

• 最值问题: 先判断 dp[n][cap] 是否仍等于无穷, 是则说明无法恰好装满, 按题意返回 -1 或特定值;
• 组合问题与存在问题: 直接返回 dp[n][cap];
• 例: 零钱兑换 1 用 Infinity 表示凑不出, 返回 -1;