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

下列代码实现了一个 0-1 背包的一维动态规划代码，内层循环是经典的逆序写法。若将内层循环改成正序遍历（即 for (int j = w[i]; j <= W; j++)），仍能得到正确答案。

int main() {
    int W = 5;
    int w[] = {2, 3, 4};
    int v[] = {10, 1, 1};
    int n = 3;
    int dp[6] = {0};

    for (int i = 0; i < n; i++) {
        for (int j = W; j >= w[i]; j--) {  // < 逆序!
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[W];
}

背包问题：01背包倒序枚举容量，完全背包正序枚举容量。状态 dp[i][j] 表示前i个物品容量j的最大价值。

01背包内层循环必须从大到小枚举容量，保证每个物品只用一次。完全背包从小到大枚举，物品可用无限次。

【考点】动态规划｜0-1背包｜完全背包｜数组状态更新

🎯 考纲定位：GESP六级动态规划模块核心题型，命题人卡住的是考生对"空间压缩"与"状态依赖"的混淆，多数人只记逆序口诀，却不明其物理意义。

🧠 解题思维：0-1背包一维DP必须逆序，因为dp[j-w[i]]需取自上一轮（不含当前物品i）。若改为正序，dp[j-w[i]]在本轮已被更新，导致物品i被多次计入，违背"每件至多一次"约束。命题人利用考生对"一维DP空间压缩"的机械记忆，错误选项A诱使考生只关注循环语法变化，却忽略状态依赖的时序性。

🪤 陷阱拆解：选项A利用考生机械记忆，误以为循环方向改变不影响结果；最阴险细节是"仍能得到正确答案"这一表述，暗示正序能自动处理重复选取，实则完全无法避免状态污染。

🔄 反命题思维：若将w[i]改为负数，正序遍历将导致无限循环或状态震荡，证明方向选择与数值符号强绑定。