思路
因为数据加大,三重循环会超时,这时候需要用到二进制优化转为01背包
设某件物品$i$ 的$si$ = 7 , 二进制为$111$ , $2^0 = 1, 2 ^ 1 = 2, 2 ^ 2 = 4$
此时我们将该物品拆分,
k = 1即当成1件物品($wi * 1,vi * 1$),
k = 2当成一件物品($wi * 2,vi * 2$),
k = 4当成一件物品($wi * 4,vi * 4$)
我们就可以 任意选 这被拆分得到的三件物品 凑成所有的情况,即选该物品i被选任意一个数量的情况
注意:
这些被拆分的物品,已经是像01背包一样,互不干涉的,并且只能选一次
例如:
$0= 0,1 = 1, 2= 2, 3 = 1 + 2, 4 = 4, 5 = 1 + 4, 6 = 2 + 4, 7 = 1 + 2 + 3$
再比如另一个物品i, $si = 11$, 就必须拆成$ k = 1, k =2 , k = 4 , k =4$
任意选这些被拆分得到的物品同样可以凑出所有情况, 即 0 ~ 11的所有情况
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 12010, M = 2010;
int n, m;
int v[N], w[N];
int f[M];
int main(){
cin >> n >> m;
//被拆分的所有物品数量
int cnt = 0;
for(int i = 1; i <= n; i ++){
int a, b, s;
cin >> a >> b >> s;
int k = 1;
while(k <= s){
cnt ++;
//每个被拆掉得成物品的权值
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
//11 : 1 2 4 4多出的4
if(s > 0){
cnt ++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for(int i = 1; i <= n; i ++) //01背包
for(int j = m; j >= v[i]; j--){
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
cout << f[m] << endl;
return 0;
}