AcWing 5. 多重背包问题 II
原题链接
中等
作者:
Value
,
2020-05-29 14:44:59
,
所有人可见
,
阅读 420
#include <iostream>
using namespace std;
const int N = 11010;
int weight[N], value[N], amount[N];
int f[N];
int main(){
int n, bag;
cin >> n >> bag;
int k = 1;
int w, v, num;
for(int i = 1; i <= n; i ++ ){
cin >> w >> v >> num;
int s = 1;
while(num >= s){
weight[k] = s * w;
value[k ++ ] = s * v;
num -= s;
s *= 2;
}
if(num){
weight[k] = num * w;
value[k ++ ] = num * v;
}
}
for(int i = 1; i < k; i ++ ){
for(int j = bag; j >= weight[i]; j -- ){
f[j] = max(f[j], f[j - weight[i]] + value[i]);
}
}
cout << f[bag] << endl;
return 0;
}