AI题库 · GESP-C++六级题库
题目分享 #20443
以下代码实现了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];
}
A
dp[i-1][j], values[i-1]
B
dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1]
C
dp[i][j-1], values[i-1]
D
dp[i-1][j - weights[i-1]] + values[i-1], dp[i][j-1]
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。