题目描述
有 $N$ 种物品和一个容量是 $V$ 的背包。
第 $i$ 种物品最多有 $s_i$ 件,每件体积是 $v_i$,价值是 $w_i$。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数,$N,V$ $(0 \lt N \le 1000$, $0 \lt V \le 20000)$,用空格隔开,分别表示物品种数和背包容积。
接下来有 $N$ 行,每行三个整数 $v_i, w_i, s_i$,用空格隔开,分别表示第 $i$ 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
数据范围
$0 \lt N \le 1000$
$0 \lt V \le 2000$
$0 \lt v_i, w_i, s_i \le 2000$
提示
本题考查多重背包的单调队列优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例:
10
算法1
(DP) $O(n^2)$
多重背包问题朴素版显然很慢,不能满足我们的需求,那我们对此进行优化。
我们发现,数据范围扩大,导致物品数量增多,导致方法超时。
可以思考通过打包物品,来减少物品种类数量。
那如何打包物品?
有一个非常经典的优化方法——二进制优化方法。
也就是说,此时我们有 $1023$ 个物品:
1, 2, 3, ..., 1022, 1023
那我们此时打包后变成:
以下打包的每一个部分称为 块
块编号 | $1$ | $2$ | $3$ | $4$ | $…$ | $10$ |
---|---|---|---|---|---|---|
块中物品数量 | $1$ | $2$ | $4$ | $8$ | $…$ | $512$ |
最终我们对每个块做一次 01背包 即可。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 25010;
int n,m;
int v[N],w[N],f[N];
int main(){
scanf("%d%d",&n,&m);
int cnt = 0;
for(int i = 1;i <= n;i ++){
int a,b,s;
scanf("%d%d%d",&a,&b,&s);
int k = 1;
while(k <= s){
cnt ++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if(s){
cnt ++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for(int i = 1;i <= n;i ++){
for(int j = m;j >= v[i];j --){
f[j] = max(f[j],f[j - v[i]] + w[i]);
}
}
printf("%d\n",f[m]);
return 0;
}