0-1 背包：容量 W=10，4 个物品重量 1,3,4,6，价值 20,30,50,60，下面 DP 函数的输出为：
int knapsack(int W, vector<int>& weights, 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];
}
- A. 90
- B. 100
- C. 110
- D. 140
正确答案：C