GESP 七级 · GESP 202606 C++ 七级 第 7 题

下面代码是一维数组优化 $0/1$ 背包的核心片段，其中 w[i] 表示第 $i$ 件物品的重量，v[i] 表示第 $i$ 件物品的价值。横线处应填入（ ）。

for (int i = 1; i <= n; i++) {
    for (int c = W; c >= w[i]; c--) {
        __________;
    }
}

根据上下文和C++语法规则确定空缺处应填的内容，关注函数调用参数、表达式和返回值类型。

填空时注意语法完整性：分号、括号匹配、函数参数类型和个数、返回值类型。

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

本题考查动态规划中 0/1 背包的一维数组空间优化（GESP 七级 DP 模块）。命题人特意用 c 倒序循环来卡住考生：很多人知道 dp[c] = max(dp[c], dp[c - w[i]] + v[i])，却记不住为什么必须倒序——因为正序会用到刚更新过的 dp[c-w[i]]，导致物品被重复使用，直接违背 0/1 背包定义。

解题核心是识别 0/1 背包的状态转移方程。选项 A 中 dp[c + w[i]] 会越界且逻辑错误；选项 B 用 min 完全违背「价值最大化」；选项 C 直接强制取物品，忽略了「不放该物品」的情况。只有 D 同时考虑了「不放」和「放」两种选择，符合 dp[c] = max(dp[c], dp[c - w[i]] + v[i])。D 选项的 max 操作保证了在「不放该物品」（保留原 dp[c]）与「放该物品」（dp[c-w[i]]+v[i]）之间取最优。

命题人最阴险的陷阱在于两个细节：一是循环方向，正序会导致物品被重复使用（变成完全背包）；二是公式结构，选项 A 的 dp[c + w[i]] 明显越界且逻辑错误，选项 C 缺少 max 只取放了的情况。绝对化表述如选项 C 直接赋值，忽略了「不放」情况；选项 A 的 c + w[i] 在 c 倒序时可能越界，命题人故意用这种明显错误来测试审题。如果你只背结论，不看循环顺序，很容易把 dp[c] = max(dp[c], dp[c-w[i]]+v[i]) 和 dp[c] = dp[c-w[i]]+v[i] 混淆。

如果题目改成「物品可重复选」（完全背包），内层循环应改为 for(int c = w[i]; c <= W; c++)，公式不变。若改为 for(int c = w[i]; c <= W; c++) 则变成完全背包，若公式改为 dp[c] = dp[c - w[i]] + v[i] 则变成贪心，命题人通过微调循环方向与公式结构，精准定位到考生对 DP 状态更新的本质理解。刷到这类题时，先问自己：「循环方向变了会对应哪种背包变种？」——这是区分 0/1 与完全背包的关键。