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

阅读以下用动态规划解决的 0-1 背包问题的函数，假设背包的容量 $W$ 是 $10kg$，假设输入 $4$ 个物品的重量 $weights$ 分别为 $1,3,4,6$（单位为 $kg$），每个物品对应的价值 $values$ 分别为 $20,30,50,60$，则函数的输出为（ ）。

#include <iostream>
#include <vector>
using namespace std;

// 0/1背包问题
int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

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

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】动态规划｜二维数组｜状态转移方程

1. 🎯 考纲定位

本题属于动态规划（DP）经典应用题，对应 GESP 六级算法与数据结构模块中"背包问题"考点。命题人放这道题是为了卡住那些只背结论、不会看代码的学生——他们知道 0-1 背包"选或不选"，但没能力追踪代码里二维数组到底存了什么。