AcWing 5. 多重背包问题 II
原题链接
中等
作者:
forhjh
,
2021-05-09 19:45:11
,
所有人可见
,
阅读 170
//解释一下先处理v, w;
//就拿例子来说,1 2 3;
//更新的话就是
> v[1] = 1, w[1] = 2
> v[2] = 2, w[2] = 4;
//这样就表示了0 ~ 3, 不用再for (int k = 1; k <= 3; k++)
再举个例子
1 2 9 // 可以用1 2 4 3 来表示0 - 9
2 4 4 // 可以用1 2 1表示0 - 4
//分别表示体积, 价值, 个数
来更新:
v[1] = 1, w[1] = 2; //1
v[2] = 2, w[2] = 4 //2
v[3] = 4, w[3] = 8 //4
v[4] = 3, w[4] = 6 //3
// 是不是 v[1] ~ v[4] 能表示0 - 9的任意一个,w[1] ~ w[4] 能表示0 - 18的任意一个
// 省去了for (int k = 1; k <= 9; k++), 从9次优化到了4次
// 继续下去
v[5] = 2, w[5] = 4 //1
v[6] = 4, w[5] = 8 //2
v[7] = 2, w[7] = 4 //1
// 同理, v[5~7] 可以表示0 ~ 8, w[5~7] 可以表示0 ~ 16
// 以此类推
// 接下来就是把问题看作0/1背包问题
// 更新 背包数目为最终划分的数目
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25000, M = 2005;
int v[N], w[N];
int f[M];
int main()
{
int m, n;
cin >> m >> n;
//先处理一下v, w
int cnt = 0;
for (int i = 1; i <= m; i++) {
int a, b, s;
cin >> a >> b >> s;
int k = 1;
while (k <= s) {
cnt++;
v[cnt] = k * a;
w[cnt] = k * b;
s -= k;
k *= 2;
}
if (s > 0) // 说明出现了视频中讲解的73的例子
{
cnt++;
v[cnt] = s * a;
w[cnt] = s * b;
}
}
m = cnt; // 更新m, 当前m是cnt
// 一维0/1背包
for (int i = 1; i <= m; i++) {
for (int j = n; j >= v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[n] << endl;
return 0;
}