AcWing 7. 混合多重背包
原题链接
简单
作者:
1694117691
,
2022-04-28 11:08:19
,
所有人可见
,
阅读 115
混合多重背包 二维版
#include <iostream>
using namespace std;
const int N = 30100;
int w[N], v[N], kind[N];
int f[N][1010];
int main()
{
int n, m;
cin >> n >> m;
int cnt = 1;
for (int i = 1; i <= n; i ++ ) {
int a, b, c;
cin >> a >> b >> c;
c = abs(c); // -1 的 01背包转换
if (c == 0) {
kind[cnt] = 1;
v[cnt] = a;
w[cnt] = b;
cnt ++;
continue;
}
int k = 1;
while (c >= k) {
v[cnt] = k * a;
w[cnt] = k * b;
c -= k;
k *= 2;
cnt ++;
}
if (c > 0) {
v[cnt] = c * a;
w[cnt] = c * b;
cnt ++;
}
}
cnt --; // cnt 初始为1,所以需要-
for (int i = 1; i <= cnt; i ++ ) {
for (int j = 0; j <= m; j ++ ) {
f[i][j] = f[i - 1][j];
if (kind[i] == 1 && j - v[i] >= 0) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
else if (j - v[i] >= 0) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[cnt][m];
return 0;
}