AcWing 5. 多重背包问题 II
原题链接
中等
作者:
术
,
2022-06-24 10:19:12
,
所有人可见
,
阅读 237
#include <iostream>
using namespace std;
const int N = 1005 * 32, V = 2005;
int v[N], w[N], s[N];
int f[V];
int main(){
int n, m;
cin>>n>>m;
int cnt = 0;
for(int i = 0; i < n; i ++){//这里不是将其转为二进制
//而是转为1,2,4,8等的堆,这些堆任意组合可以组成1~c中的任何数
int a, b, c;
cin>>a>>b>>c;
int k = 1;
while(k <= c){
cnt ++;
v[cnt] = a * k;
w[cnt] = b * k;
c -= k;
k *= 2;
}
if(c > 0){
cnt ++;
v[cnt] = a * c;
w[cnt] = b * c;
}
}
//01
for(int i = 1; i <= cnt; i ++){
for(int j = m; j >= v[i]; j --){
// f[i][j] = f[i - 1][j];
// if(j >= v[i])
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout<<f[m];
return 0;
}