【入门】混合背包
题目描述
有 种物品和一个容量是 的背包。
物品一共有三类：
- 第一类物品只能用1次（01背包）；
- 第二类物品可以用无限次（完全背包）；
- 第三类物品最多只能用 次（多重背包）；
每种体积是 ，价值是 。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。
输入格式
第一行两个整数，，用空格隔开，分别表示物品种数和背包容积。
接下来有 行，每行三个整数 ，用空格隔开，分别表示第 种物品的体积、价值和数量。
- 表示第 种物品只能用1次；
- 表示第 种物品可以用无限次；
- 表示第 种物品可以使用 次；
输出格式
输出一个整数，表示最大价值。
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
8
提示
【样例解释 1】
- 可以选择 1 个物品2 和 1 个物品3
- 总体积为：1 * 2 + 1 * 3 = 5
- 总价值为：1 * 4 + 1 * 4 = 8
请思考后再点击查看提示
- 可以分类讨论，对于每种物品分别用 01背包，完全背包，多重背包求解
#include <bits/stdc++.h>
using namespace std;
int main() {
// 下面两句是为了让 cin 更快
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, v, w, s;
while (cin >> n >> m) {
vector<int> dp(m + 1, 0);
for (int i = 0; i < n; i++) {
cin >> v >> w >> s;
if (s == -1) { // 只能用 1 次, 01背包
for (int j = m; j >= v; j--) {
dp[j] = max(dp[j], dp[j - v] + w);
}
} else if (s == 0) { // 可以用无限次, 完全背包
for (int j = v; j <= m; j++) {
dp[j] = max(dp[j], dp[j - v] + w);
}
} else { // 可以用有限次, 多重背包, 二进制拆分
for (int d = 1; s > 0; d *= 2) {
int c = min(d, s), nv = c * v, nw = c * w;
for (int j = m; j >= nv; j--) {
dp[j] = max(dp[j], dp[j - nv] + nw);
}
s -= c;
}
}
}
cout << dp[m] << '\n';
}
return 0;
}