AcWing 7. 暴力背包问题
原题链接
中等
作者:
目目目
,
2022-01-26 16:37:42
,
所有人可见
,
阅读 663
暴力拆成01背包
完全背包可以视为这种物品的总体积大于背包容积
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, m, num;
int f[N], v[N], w[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int a, b, s;
cin >> a >> b >> s;
if (s == -1) v[++num] = a, w[num] = b;
else
{
if (s == 0) s = 1000 / a + 1; //这种物品的总体积大于背包容积的话即可视为无限个物品
int k = 1;
while (k <= s)
{
v[++num] = k * a, w[num] = k * b;
s -= k;
k *= 2;
}
if (s) v[++num] = s * a, w[num] = s * b;
}
}
for (int i = 1; i <= num; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m];
return 0;
}
二进制优化啊%%%