GESP 6级客观题｜一维动态规划与基础背包｜课堂讲解

考试频率：高频。本卷共 2 题。

1. 在解决简单背包问题时，动态规划的状态转移方程如下：（ ）
   dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]); 该方程表示：在考虑第$i$个物品时，当前背包容量为$w$，如果不放物品$i$，则最大价值是dp[i-1][w]；如果放入物品$i$，则最大价值是dp[i-1][w - weights[i-1]] + values[i-1]，其中数组$weights$和$values$分别表示所有物品的重量和价值，数组下标从0开始。

   {{ select(1) }}

• 对
• 错

2. 阅读以下⽤动态规划解决的0-1背包问题的函数，假设背包的容量 是10kg，假设输⼊4个物品的重量分别为 （单位为kg），每个物品对应的价值 分别为 ，则函数的输出为（ ）。

#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];
}

{{ select(2) }}

• 90
• 100
• 110
• 140