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

下面是一维数组实现的 0/1 背包。内层循环必须从大到小枚举容量，主要原因是（　　）。

for (int i = 0; i < n; ++i) {
for (int w = W; w >= weight[i]; --w) {
dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
}
}

看到 0/1 背包的一维 DP 写法，第一反应是"为什么内层循环要从大到小"。因为一维数组复用，如果从小到大枚举容量，当前物品会被重复使用（相当于完全背包）。从大到小枚举，确保每次更新 dp[w] 时，dp[w-weight[i]] 还是上一轮的值，这样每件物品最多被选一次。这是 0/1 背包空间优化的核心技巧。

选项 B 混淆了"容量枚举顺序"和"物品选择顺序"，实际上物品是按外层循环顺序考虑的；选项 C 偷换概念，时间复杂度 O(nW) 与循环方向无关；选项 D 看似合理，但越界由条件 w>=weight[i] 保证，与方向无关。最阴险的是命题人把"完全背包"的写法混进来，让考生误以为从小到大也能用。

1. 考纲定位

本题考查 GESP 六级《动态规划》模块中"背包问题"的变形应用。命题人专门卡住"一维 DP 空间优化"这个考点——绝大多数考生背过"0/1 背包要倒序"，但说不清为什么。这道题就是考这个"为什么"。

2. 解题思维

看到 0/1 背包的一维 DP 写法，第一反应是"为什么内层循环要从大到小"。因为一维数组复用，如果从小到大枚举容量，当前物品会被重复使用（相当于完全背包）。从大到小枚举，确保每次更新 dp[w] 时，dp[w-weight[i]] 还是上一轮的值，这样每件物品最多被选一次。这是 0/1 背包空间优化的核心技巧。