题解 | #【模板】完全背包#
【模板】完全背包
https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=308&tqId=2032575&ru=/exam/oj&qru=/ta/algorithm-start/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D308
开始逐渐理解
#include <iostream>
#include <vector>
#include <climits>
int main(int argc, char *argv[]) {
int count, size;
std::cin >> count >> size;
std::vector<std::vector<int>> objs(count, std::vector<int>(2, 0));
for (int i = 0; i < count; ++i) {
std::cin >> objs[i][0] >> objs[i][1];
}
// dp[i] 表示容量为i的背包所能装的最大价值
std::vector<int> dp(size + 1, 0);
for (int i = 0; i < count; ++i) {
for (int j = objs[i][0]; j <= size; ++j) {
dp[j] = std::max(dp[j], dp[j - objs[i][0]] + objs[i][1]);
}
}
std::cout << dp[size] << std::endl;
for (int i = 1; i < dp.size(); ++i) {
dp[i] = INT_MIN;
}
dp[0] = 0;
for (int i = 0; i < count; ++i) {
for (int j = objs[i][0]; j <= size; ++j) {
dp[j] = std::max(dp[j], dp[j - objs[i][0]] + objs[i][1]);
}
}
if (dp[size] < 0) {
std::cout << 0 << std::endl;
} else {
std::cout << dp[size] << std::endl;
}
return 0;
}