GESP 七级 · GESP202609 C++ 七级 第 22 题

为解决 0/1 背包问题，使用一维数组优化时，内层容量循环应从大到小枚举。

看到0/1背包先想二维dp[i][j]，优化成一维dp[j]后，更新dp[j]依赖dp[j-w]，必须保证dp[j-w]是上一轮的值。因此容量循环必须从大到小枚举，否则同一物品会被重复使用。

易与完全背包混淆（完全背包容量从小到大），或误以为循环方向不影响结果。命题人利用"一维数组优化"这一条件，考察对状态依赖顺序的精确理解，属于经典陷阱。

考纲定位 本题考查《GESP 考试大纲》动态规划模块（七级核心考点）。命题人放这道题，是因为绝大多数考生能写出二维递推式，却在一维空间优化时搞错循环方向——这是区分"会DP"和"真懂DP"的分水岭。

解题思维 0/1背包的二维状态是dp[i][j]（前i件物品、容量j的最大价值），转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。优化成一维数组dp[j]后，dp[j]更新时依赖的是dp[j-w[i]]。若容量从小到大枚举，dp[j-w[i]]可能已被本轮更新（即已包含当前物品），导致同一物品被重复使用；只有从大到小枚举，才能保证dp[j-w[i]]仍是上一轮的值。

陷阱拆解 选项B的错误设计源于两个常见误区——一是把0/1背包和完全背包搞混（完全背包容量确实从小到大），二是认为"循环方向不影响最终结果"。命题人特意强调"一维数组优化"，就是在考察对状态依赖顺序的精确理解，属于经典陷阱。

反命题思维 如果把题中"0/1背包"改成"完全背包"，答案就反了（应从小到大）；如果把"一维数组"改成"二维数组"，循环方向就无所谓了。这说明命题人精准地卡住了考生对DP状态依赖顺序的理解深度。