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

给定 $ n $ 个物品和一个最大承重为 $ W $ 的背包，每个物品有一个重量 $ wt[i] $ 和价值 $ val[i] $，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 $ W $。关于下面代码，说法正确的是（ ）。

int knapsack1D(int W, vector<int>& wt, vector<int>& val, int n) {
    vector<int> dp(W+1, 0);
    for (int i = 0; i < n; ++i) {
        for (int w = W; w >= wt[i]; --w) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

STL 容器：vector（动态数组）、set/map（红黑树，有序）、unordered_set/map（哈希表，无序）。注意迭代器失效问题。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】动态规划（0/1 背包）｜一维数组优化｜遍历方向依赖

考纲定位：本题考查 GESP 六级动态规划模块的核心考点——0/1 背包的一维状态压缩。命题人特意把经典二维解法压缩成一行代码，就是卡住那些只背"用一维数组就能解决背包"结论，却不理解遍历顺序背后状态依赖的考生。

解题思维：看到 0/1 背包的一维实现，第一反应应该是"为什么内层要从大到小遍历？"因为 dp[w] 依赖 dp[w-wt[i]]，如果从小到大遍历，w-wt[i] 可能已经被当前物品 i 更新过，导致同一物品被重复使用。正确做法是：外层物品 i 从 0 到 n-1，内层容量 w 从 W 到 wt[i]，确保每次状态更新都只用前 i-1 个物品的信息。这是状态压缩类动态规划的通法，适用于所有一维数组优化问题。

陷阱拆解：选项 A 错在忽略容量为 0 时数组访问边界——dp[0] 始终为 0，循环不执行，逻辑自洽。选项 B 错在循环变量混淆，它把"物品"和"容量"的角色颠倒了。选项 D 是语义陷阱，把"最大价值"偷换成"最小重量"，显然与代码意图相反。最阴险的是 C 的反面——如果你只背"一维数组优化"的结论，而不理解"遍历方向"对状态依赖的影响，就会误以为"从小到大"也行，结果在完全背包或类似题目中掉坑。

反命题思维：如果把这道题改成"完全背包"（物品可无限使用），内层循环方向就要反过来（从小到大），否则就会变成 0/1 背包。或者把二重循环改成三重循环（考虑物品数量限制），再问"若 wt[i] 为 0 会发生什么？"这些变式都是命题人常用的手法，用来测试你对状态转移本质的掌握程度。所以，刷到类似题时，先问自己"我是用一维还是二维？遍历方向是从小到大还是从大到小？依赖的是前 i-1 还是包括 i？"