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