AcWing 7. 混合背包问题
原题链接
中等
作者:
fancywing
,
2021-01-19 15:08:38
,
所有人可见
,
阅读 396
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;
int k = 1;
// 01背包和完全背包转换成多重背包问题,再将多重背包转化成一个个的二进制01背包来做即可
if(s == -1) s = 1; // 最多为1个
else if(s == 0) s = m / v; // 最多为m / v个
// else if(s > 0) s = s; // 最多为s个
while(k <= s){
V[cnt] = k*v;
W[cnt] = k*w;
s -= k;
k *= 2;
cnt++;
}
if(s > 0){
V[cnt] = s *v;
W[cnt] = s *w;
cnt++;
}
}
//多重背包转化成二进制01背包来做
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]<<endl;
return 0;
}