GESP 六级 · GESP 202412 C++ 六级 第 15 题

假设背包的最大容量 $W = 8kg$，共有有 4 个物品可供选择，4 个物品的重量分别为 $weights = [2, 3, 5, 7]$，对应的价值分别为 $values = [30, 40, 60, 80]$，则该 0/1 背包问题中，背包的最大价值为（ ）。

背包问题：01背包倒序枚举容量，完全背包正序枚举容量。状态 dp[i][j] 表示前i个物品容量j的最大价值。

01背包内层循环必须从大到小枚举容量，保证每个物品只用一次。完全背包从小到大枚举，物品可用无限次。

【考点】0/1 背包｜动态规划｜状态转移方程

🎯 考纲定位 【考点】0/1 背包｜动态规划｜状态转移方程。命题人把这道题放在六级，就是卡住那些只会暴力枚举的考生——面对 4 个物品时，$2^4=16$ 种组合看似能枚举完，但一旦物品数量上升到 10-20，指数爆炸会让程序超时。这道题的本质是考察你是否能想到用二维数组 $dp[i][j]$ 表示"前 i 件物品放进容量 j 的背包能得到的最大价值"，这是从小学奥数"称重问题"到算法竞赛 DP 的跨越。

🧠 解题思维 看到"最大价值"和"容量限制"，第一时间想到动态规划。定义 $dp[i][j]$ 表示前 i 件物品放入容量 j 的背包能得到的最大价值，状态转移方程是 $dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])$（若 $j \ge w[i]$）。逐个物品迭代，容量从 0 到 8 更新即可。这道题的解法通法就是：遇到"在有限资源下选最优"的题目，优先构造二维 DP 表，因为 $O(nW)$ 的时间复杂度总是优于 $O(2^n)$ 的暴力枚举。

🪤 陷阱拆解 选项 A、B、D 都是精心设计的"计算陷阱"。A=70 是只选了前两个物品（2+3=5≤8，价值 30+40=70，可行但非最优）；B=90 是选了 0 号与 2 号（2+5=7≤8，价值 30+60=90，可行但非最优）；D=120 是选了 1 号与 2 号（3+5=8≤8，价值 40+60=100，可行但非最优）。最阴险的是 C=100，它恰好是选了 1 号与 2 号（3+5=8≤8，价值 40+60=100），这是唯一达到 100 的组合。如果你只盯着"最大价值"而不检查重量是否超，就会误选 D；如果你只背"0/1 背包公式"而不代入具体数字，就会算错。

🔄 反命题思维 命题人如果想换个考法，可以把"0/1 背包"改成"完全背包"（物品可重复选），此时容量 8kg 下，最优解会变成 2+2+2+2=8，价值 30×4=120，答案就从 C 变成 D。或者改成"分数背包"（可切分），按价值密度排序，先拿密度最高的 7kg 物品（80/7≈11.4），再拿 1kg 的 3kg 物品（40/3≈13.3），总价值 80+13.3=93.3，答案就变成 B。刷到类似题时，先问自己："题目到底限制了物品不能重复选吗？"