AcWing 7. 混合背包问题
原题链接
中等
作者:
烟花易冷
,
2020-09-19 15:55:30
,
所有人可见
,
阅读 530
#include <iostream>
#include <algorithm>
using namespace std;
int N, V, num, cnt = 1;
int w[1111], v[1111], s[1111], dp[1111];
int new_w[11111], new_v[11111];
int main()
{
cin >> N >> V;
for (int i = 1; i <= N; i++)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= N; i++)
{
if (s[i] == -1)
{
new_v[cnt] = v[i];
new_w[cnt++] = w[i];
}
else if (s[i] > 0)
{
for (int j = 1; j < s[i]; j <<= 1)
{
new_v[cnt] = j * v[i];
new_w[cnt++] = j * w[i];
s[i] -= j;
}
if (s[i])
{
new_v[cnt] = s[i] * v[i];
new_w[cnt++] = s[i] * w[i];
}
}
else if (s[i] == 0)
{
num = 0;
while (num * v[i] <= V)
num++;
for (int k = 1; k < num; k <<= 1)
{
new_v[cnt] = k * v[i];
new_w[cnt++] = k * w[i];
num -= k;
}
if (num)
{
new_v[cnt] = num * v[i];
new_w[cnt++] = num * w[i];
}
}
}
for (int i = 1; i <= cnt; i++)
for (int j = V; j >= new_v[i]; j--)
dp[j] = max(dp[j], dp[j - new_v[i]] + new_w[i]);
cout << dp[V];
system("pause");
return 0;
}