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

下列代码是一维数组优化 0/1 背包的核心片段，执行后 dp[8] 的输出结果是（　　）。

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int w = 3, v = 5, W = 8;
int dp[9] = {0};
for (int c = W; c >= w; c--)
dp[c] = max(dp[c], dp[c - w] + v);
cout << dp[8] << endl;
return 0;
}

看到一维数组优化背包题，先想容量循环方向。正向会重复选，反向才保证每个物品只选一次。

选项 A 是忘了初始化，B 是只算一次，C 是正向遍历导致重复选。

1. 考纲定位

本题考查 GESP 七级"动态规划"模块中"一维数组优化 0/1 背包"的核心考点。命题人专门设计这道题，卡住的是考生对"反向遍历"这一关键细节的掌握——绝大多数人背下 dp[c] = max(dp[c], dp[c-w] + v) 公式，却忽略循环方向对状态依赖的影响。

2. 解题思维

看到一维数组优化背包题，先想容量循环方向。正向会重复选，反向才保证每个物品只选一次。