AcWing 7. 混合背包问题
原题链接
中等
作者:
fancywing
,
2021-01-20 09:40:06
,
所有人可见
,
阅读 436
C++ 代码
#include<iostream>
using namespace std;
const int N = 100010;
int f[N],V[N], W[N];
int main(){
int n,m;
cin >> n >> m;
int cnt = 1;
for(int i = 1; i<=n; i++){
int v,w,s;
cin>>v>>w>>s;
// 完全背包问题
if(s == 0){
for(int j = v; j <= m; j++){
f[j] = max(f[j], f[j-v] + w);
}
}
else {
// 01背包为特殊的多重背包
if(s == -1) s = 1;
// 多重背包二进制优化版
for(int k = 1; k <= s; k *= 2){
for(int j = m; j >= k*v; j--)
f[j] = max(f[j], f[j - k*v] + k * w);
s -= k;
}
// 处理尾数
if(s){
for(int j = m; j >= s * v; j--)
f[j] = max(f[j], f[j - s * v] + s * w);
}
}
}
cout<< f[m]<<endl;
return 0;
}