题目
有 种物品和一个容量是 的背包。
物品一共有三类:
- 第一类物品只能用1次(01背包);
- 第二类物品可以用无限次(完全背包);
- 第三类物品最多只能用 次(多重背包);
每种体积是 ,价值是 。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数, ,用空格隔开,分别表示物品种数和背包容积。
接下来有 行,每行三个整数 ,用空格隔开,分别表示第 种物品的体积、价值和数量。
- 表示第 种物品只能用1次;
- 表示第 种物品可以用无限次;
- 表示第 种物品可以使用 次;
输出格式
输出一个整数,表示最大价值。
数据范围
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例:
8
解题
方法一:多重背包 + 二进制优化
思路
把01背包的物品看作最大数量只有 的物品,把完全背包的物品看作最大数量有 的物品( 表示背包容量, 表示该物品单个的体积),然后根据数据范围( )发现用朴素的多重背包解法会超时,但是用二进制优化或单调队列优化都可以解决。
小技巧:C++中, !~x
在 时为 。(因为对 取反得 , 隐式转换为 ,否 等于 )
代码
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1010, M = N * ceil(log2(N)) + 10;
int n, c;
int v[M], w[M];
int cnt;
int f[N];
int main() {
scanf("%d%d", &n, &c);
for (int i = 0; i < n; ++i) {
int vi, wi, si;
scanf("%d%d%d", &vi, &wi, &si);
if (!~si) si = 1;
if (!si) si = c / vi + 1;
for (int x = 1; si >= x; ++cnt, si -= x, x <<= 1) {
v[cnt] = x * vi;
w[cnt] = x * wi;
}
if (si > 0) {
v[cnt] = si * vi;
w[cnt] = si * wi;
++cnt;
}
}
for (int i = 0; i < cnt; ++i) {
for (int j = c; j >= v[i]; --j) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
printf("%d\n", f[c]);
return 0;
}
方法二:多重背包 + 单调队列优化
思路
如上所述,可以用单调队列优化。
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n, c;
int f[N], g[N];
int que[N];
int hh, tt;
int main() {
scanf("%d%d", &n, &c);
for (int i = 0; i < n; ++i) {
int v, w, s;
scanf("%d%d%d", &v, &w, &s);
if (!~s) s = 1;
if (!s) s = c / v + 1;
memcpy(g, f, sizeof(f));
for (int r = 0; r < v; ++r) {
hh = 0, tt = -1;
for (int j = r; j <= c; j += v) {
while (hh <= tt && (j - que[hh]) / v > s) ++hh;
while (hh <= tt && g[j] >= g[que[tt]] + (j - que[tt]) / v * w) --tt;
que[++tt] = j;
f[j] = g[que[hh]] + (j - que[hh]) / v * w;
}
}
}
printf("%d\n", f[c]);
return 0;
}
评论区