GESP 6级客观题｜一维动态规划与基础背包｜课后作业

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

1. 以下代码实现了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];
}

{{ select(1) }}

• dp[i-1][j], values[i-1]
• dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1]
• dp[i][j-1], values[i-1]
• dp[i-1][j - weights[i-1]] + values[i-1], dp[i][j-1]

2. 状态转移⽅程是动态规划的核⼼，可以通过递推⽅式表⽰问题状态的变化。

   {{ select(2) }}

• 对
• 错

3. 给定 $n$ 个物品和一个最大承重为 $W$ 的背包，每个物品有一个重量 $w_i$ 和价值 $v_i$，每个物品只能选择放或不放。目标是选择若干个物品放入背包，使得总价值最大，且总重量不超过 $W$。关于下面代码，说法正确的是（ ）。

int knapsack1D(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) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

{{ select(3) }}

• 该算法不能处理背包容量为 0 的情况
• 外层循环 $i$ 遍历背包容量，内层遍历物品
• 从大到小遍历 $w$ 是为了避免重复使用同一物品
• 这段代码计算的是最小重量而非最大价值

4. 下面代码采用动态规划求解零钱兑换问题：给定 $n$ 种硬币，第 $i$ 种硬币的面值为 $coins[i-1]$，目标金额为 $amt$，每种硬币可以重复选取，求能够凑出目标金额的最少硬币数量；如果不能凑出目标金额，返回 -1。

int coinChangeDPComp(vector<int> &coins, int amt) {
    int n = coins.size();
    int MAX = amt + 1;
    vector<int> dp(amt + 1, MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int a = 1; a <= amt; a++) {
            if (coins[i - 1] > a)
                dp[a] = dp[a];
            else
                dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1);
        }
    }
    return dp[amt] != MAX ? dp[amt] : -1;
}

{{ select(4) }}

• 对
• 错

5. 给定 $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];
}

{{ select(5) }}

• dp[w] = max(dp[w], dp[w] + val[i]);
• dp[w] = dp[w - wt[i]] + val[i];
• dp[w] = max(dp[w - 1], dp[w - wt[i]] + val[i]);
• dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

6. 下面代码实现了动态规划版本的斐波那契数列计算，其时间复杂度是 $O(n)$。

int fib_dp(int n) {
    if (n <= 1) return n;
    vector<int> dp(n+1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

{{ select(6) }}

• 正确
• 错误