背包问题教学
2026-10-05 19:01:43
发布于：湖南
10阅读
0回复
0点赞
背包与建模（复赛冲刺·第一 讲）
一、核心知识点精讲
- 本讲定位
在 大纲（2025年修订版）中，入门级「4. 算法」板块明确列出了 动态规划（一维、背包、区间） 这一条目。
近五年（2021—2025）复赛的 20 道题中，位置出现了 3 次动态规划：
也就是说： T4 是目前**区分度最高、也最容易成为「爆零分水岭」的位置。**而背包是入门级 DP 中最容易 建模、最容易拿分、也最容易考到的一类。前面 15 讲中，第 14 课讲了线性 DP 与树形 DP，但背包几乎 是一片空白——本讲把这块补齐。
1. DP 建模四步法
背包问题本质上是一类「选择」问题： 一堆物品，每件物品有体积（代价）和价值（收益），在容量限 制下做最优选择。 遇到背包，先回答下面四个问题：
建模口诀：
「代价当体积， 收益当价值；求最大用，求方案用；倒着跑，完全正着跑。」
2. 0/1 背包（每件物品选或不选）
问题：有件物品，第件体积、价值；背包容量。每件物品最多选一次，求最大总价值。
原始二维状态 ：表示前件物品、容量不超过的最大价值。
滚动数组优化（一维写法） ：
for (int i = 1; i <= n; i++)
for (int j = W; j >= w[i]; j--) // ★ 倒序！
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
为什么必须倒序？
要由「上一轮（不含第件）」的推出。若正序枚举，会在本轮 已经被第件物品更新过，相当于第件被用了多次——那就变成完全背包了。倒序保证左侧的仍是上一轮的旧值。
记忆方法：倒序 = 每件只能用一次。
3. 完全背包（每件物品可选无限次）
问题：与0/1背包相同，但每件物品可以选任意多次。
转移：
，注意第二项是（本轮），因为可以继续选第件。
一维写法：只要把 0/1 背包的循环改成正序即可。
for (int i = 1; i <= n; i++)
for (int j = w[i]; j <= W; j++) // ★ 正序
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
正序枚举时已经是本轮更新过的值，等价于「第件物品可以反复选」，恰是完全背包的语义。
一句话总结：同一段代码，倒序 0/1，正序完全。这是最容易考、也最容易写错的一行。
这里空空如也
有帮助，赞一个