GESP 六级 · GESP 202503 C++ 六级 第 13 题

以下代码实现了 0/1 背包问题的动态规划解法。假设物品重量为 weights[]，价值为 values[]，背包容量为 $W$，横线上应填写（ ）。

int knapsack(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (weights[i-1] > j) {
                dp[i][j] = dp[i-1][j]; // 当前物品装不下
            } else {
                dp[i][j] = max(__________________); // 在此处填入代码
            }
        }
    }

    return dp[n][W];
}

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

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

【考点】二维 DP｜0/1 背包｜状态转移

GESP 六级 DP 模块的标志性题型。命题人卡住的是"背公式但不会写代码"的选手——他们知道要取 max，却记不清两个候选状态的正确顺序。

标准 0/1 背包的转移是：对每个物品 i 和容量 j，要么不装（dp[i-1][j]），要么装（dp[i-1][j-weights[i-1]]+values[i-1]）。else 分支必须把这两个值传给 max，而不是只传一个。

逐项拆错：A、C 都只给了一个候选，max 缺参数；D 把 dp[i][j-1] 当候选，这是把二维表看成了滚动数组，顺序全错。只有 B 同时给出"不装"和"装"的两种可能，且数组下标与循环变量 i-1 对齐。

换个考法：若把二维表改成一维 dp[j] 会怎样？此时转移要写为 max(dp[j], dp[j-weights[i-1]]+values[i-1])，因为上一行已被覆盖。再比如把"装不下"判断改成 weights[i-1]<=j，陷阱就变成"边界容量取等"的语义陷阱。

刷到类似题先自问：dp 的横向是容量还是物品？纵向是物品还是容量？i-1 一定指上一行，j-1 才指上一列。答对这两个问题，答案自然浮现。