最好用二进制优化的多重背包,三层循环可能超时
```cpp
//
#include<bits/stdc++.h>
using namespace std;
int n,m,v[1100010],w[1001010],f[200010];
int main(){
//
cin>>n>>m;
int cnt=1;
for(int i=1;i<=n;i++){
int a,b,s;
cin>>a>>b>>s;
for(int k=1;k<=s;k*=2){
w[cnt]=a*k;
v[cnt]=b*k;
cnt++;
s-=k;
}if(s>0){
w[cnt]=s*a;
v[cnt]=s*b;
cnt++;
}
}for(int i=1;i<=cnt;i++){
for(int j=m;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}cout<<f[m];
return 0;
}
/*
*/
```
by fried_chicken @ 2024-05-03 10:37:54
@[fried_chicken](/user/673342) 谢谢,已关
by Change_YuAN @ 2024-05-03 10:43:28
@[Change_YuAN](/user/1140231)
~~czy 姐姐贴贴~~
二进制优化其实挺简单的。
根据位值原理,在二进制下,一个正整数 $x$ 显然可以表示为 $2^{p_1}+2^{p_2}+\ldots +2^{p_k}$ 的形式,其中 $p_1, p_2, \ldots, p_k$ 互不相同。所以考虑把物品拆成 $(2^{p_i} \times w, 2^{p_i} \times w)$ 的形式,跑 01 背包即可。
by 心灵震荡 @ 2024-05-03 12:07:45
~~你干嘛,哈嗨呦(重温经典)~~
懂了,谢谢
by Change_YuAN @ 2024-05-03 14:27:53