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

给定 $ n $ 个物品和一个最大承重为 $ W $ 的背包，每个物品有一个重量 $ wt[i] $ 和价值 $ val[i] $，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 $ W $，则横线上应填写（ ）。

int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
    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六级动态规划核心题型。命题人卡在考生对「0/1背包状态转移」的机械记忆——背下公式却分不清max两边的物理意义，这是区分合格与优秀选手的试金石。

看到循环结构先定位：外层i遍历物品，内层w逆序遍历容量（防重复选）。这是背包问题的「一维数组优化」标志。核心观察：dp[w]表示容量w下的最优值，当前物品i有两种选择——不选（dp[w]不变）或选（dp[w-wt[i]]+val[i]）。因此空格必须同时保留旧值并尝试新值，用max取最优。

A选项dp[w]+val[i]毫无意义——把当前最优值与物品价值相加？这违反背包定义。B选项直接赋值，若dp[w]原本更大会被错误覆盖。C选项dp[w-1]偷换概念：容量w-1的最优值与当前容量w的决策无关。只有D同时保留旧值dp[w]与尝试新值dp[w-wt[i]]+val[i]，符合状态转移方程。

命题人若把max换成min，就变成求最小价值；若去掉dp[w]，则退化为完全背包（允许重复选）。刷到类似题先问：当前状态是否依赖上一轮？需要max还是min？