1. $0/1$ 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（ ）。

for each item (w, v):
    for (int j = W; j >= w; --j)
        dp[j] = max(dp[j], dp[j-w] + v);

{{ select(1) }}

• 内层 $j$ 必须从小到大，否则会漏解
• 内层 $j$ 必须从大到小，否则同一件物品会被用多次
• $j$ 从大到小或从小到大都一样
• 只要 dp 初始为 $0$，方向无所谓

2. 下面代码实现 $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];
}

{{ select(2) }}

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

3. 给定 $n$ 个物品和一个最大承重为 $W$ 的背包，每个物品有重量 wt[i] 和价值 val[i]，每件物品只能选或不选。关于下面的一维 $0/1$ 背包代码，说法正确的是（ ）。

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. 以下代码实现了 $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(4) }}

• 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]

5. 假设背包的最大容量 $W=8kg$，共有有 4 个物品可供选择，4 个物品的重量分别为 $weights=[2,3,5,7]$，对应 的价值分别为 $values=[30,40,60,80]$，则该$0/1$背包问题中，背包的最大价值为（ ）。 {{ select(5) }}

• 70
• 90
• 100
• 120

6. 对0-1背包问题，贪心算法一定能获得最优解。 {{ select(6) }}

• 正确
• 错误

7. 完全背包允许物品无限选取，滚动数组优化后，表示背包容量的变量需要倒序遍历。（） {{ select(7) }}

• 正确
• 错误

8. 下面代码采用动态规划求解零钱兑换：给定若干硬币面值 coins，目标金额 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(8) }}

• 正确
• 错误

9. 上题属于0/1背包问题。 {{ select(9) }}

• 正确
• 错误

10. 在动态规划解决一维硬币找零问题时，若硬币面额为 [1, 3, 4]，目标金额为 6，则最少需要 2 枚硬币（3+3）。

{{ select(10) }}

• 正确
• 错误