GESP 六级 · GESP 202606 C++ 六级 第 15 题

下面代码实现 $0/1$ 背包的一维动态规划。第 $i$ 个物品重量为 wt[i]，价值为 val[i]，背包容量为 $W$。横线处应填写（ ）。

int knapsack(int W, vector<int>& wt, vector<int>& val) {
    int n = wt.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int w = W; w >= wt[i]; --w) {
            __________________________
        }
    }
    return dp[W];
}

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

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

【考点】0/1 背包｜动态规划｜空间优化

🎯 考纲定位

GESP 六级《算法与数据结构》模块，具体对应"动态规划"中"背包问题"的考点。命题人放这道题就是卡住那些只背模板但不懂推导过程的考生——他们看到"背包"就条件反射地写 dp[w]=max(dp[w],dp[w-wt[i]]+val[i])，却说不清为什么内层循环要从大到小遍历。