AcWing 5. 多重背包问题 II
原题链接
中等
C++ 代码
// 转化为01背包问题,更进一步用二进制优化
// 某种物品有7个,则拆成1,2,4;有9个则拆成1,2,4,2
#include <iostream>
using namespace std;
const int N = 24000;
int f[N]; // 二维数组优化为一维,因为状态传递只涉及原来二维数组的相邻两行
int w[N],v[N],s[N];
int n, V;
int main() {
cin >> n >> V;
int cnt = 0;
for(int i = 0;i < n; i ++) {
int v1, w1, s;
cin >> v1 >> w1 >> s;
int k = 1;
while(k <= s) {
w[cnt] = k * w1;
v[cnt] = k * v1;
s -= k;
k *= 2;
cnt ++;
}
if(s > 0) {
w[cnt] = s * w1;
v[cnt] = s * v1;
cnt ++;
}
}
n = cnt;
for(int i = 0; i < n; i ++) {
for(int j = V; j >= v[i]; j --) {
f[j] = max(f[j], f[j-v[i]] + w[i]);
}
}
cout << f[V] << endl;
return 0;
}