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

下列一维动态规划代码实现的是完全背包问题，因为在处理第 i 种物品时，同一种物品可能被重复选择。

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

看到双层循环先盯内层方向：0/1背包内层倒序，完全背包内层正序。本题内层从 weight[i] 到 W 递增，说明同种物品可重复选，符合完全背包特征。再验证状态转移方程 dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) 是否匹配，匹配则判定正确。

1. 考纲定位

本题出自 GESP 六级《算法与数据结构》模块，对应"动态规划"专题中的背包问题子集。命题人刻意选择完全背包而非 0/1 背包，就是要卡住考生对"内层循环方向决定物品复用性"这一核心机制的理解。六级考生普遍能写出背包框架，但 70% 以上会混淆 0/1 与完全背包的遍历顺序，这道题就是专门测试这个知识盲点。

2. 解题思维

代码外层 for (int i = 0; i < n; ++i) 按物品种类顺序处理，内层 for (int w = weight[i]; w <= W; ++w) 从当前物品重量开始正向遍历到总容量。这个正向遍历是关键——当处理到容量 w 时，dp[w - weight[i]] 已经包含了当前物品 i 被选中的情况，因此 dp[w] = max(dp[w], dp[w - weight[i]] + value[i]) 允许同种物品被多次加入。

状态转移方程完全匹配完全背包的标准形式：dp[w] 表示容量 w 下的最大价值，每次用 dp[w - weight[i]] + value[i] 尝试更新。若内层改为倒序（从 W 到 weight[i]），则 dp[w - weight[i]] 尚未包含物品 i，就变成了 0/1 背包。