背包容量W=10,物品重量为[1,3,4,6]、价值为[20,30,50,60]时,如下0-1背包C++函数的输出结果为?
#include <iostream>
#include <vector>
using namespace std;
// 0/1背包问题
int knapsack(int W, const vector<int>& weights, const 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];
}
正在加载题目数据…
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析