完全背包直接模拟,多重背包拆分成二进制,通过二进制枚举,0001,0010,0100,1000,如果有剩下的直接用01背包模拟
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N], s[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i++)
{
if (!s[i])
{
for (int j = v[i]; j <= m; j++)
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
else
{
if (s[i] == -1)s[i] = 1;
for (int k = 1; k <= s[i]; k *= 2)
{
for (int j = m; j >= k * v[i]; j--)
{
f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
}
s[i] -= k;
}
if (s[i])
{
for (int j = m; j >= s[i] * v[i]; j--)
{
f[j] = max(f[j], f[j - s[i] * v[i]] + s[i] * w[i]);
}
}
}
}
cout << f[m] << endl;
return 0;
}