华为9月2号笔试第三题(货车搬家)是不是有问题
这题是标准的01背包问题没有任何变形,但是只能过80%
求教
int main() {
int k, n;
cin >> k >> n;
vector<int> v;
vector<int> w;
int tmp = 0;
for (int i = 0; i < n; i++) {
cin >> tmp;
w.push_back(tmp);
}
for (int i = 0; i < n; i++) {
cin >> tmp;
v.push_back(tmp);
}
vector<int> dp(k + 1, 0);
for (int j = 0; j < n; j++) {
int tmpw = w[j];
int val = v[j];
for (int r = k; r >= tmpw; --r) {
dp[r] = max(dp[r], dp[r - tmpw] + val);
}
}
cout << *max_element(dp.begin(), dp.end()) << endl;
}
查看18道真题和解析
