题目描述
多重背包问题 Level 2
代码
#include <iostream>
#include <vector>
using namespace std;
#define x first
#define y second
using PII = pair<int, int>;
const int N = 11010;
int f[N];
vector<PII> item;
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
int v1, w1, s1;
cin >> v1 >> w1 >> s1;
int j = 1;
while (j <= s1)
{
PII temp(v1 * j, w1 * j);
item.push_back(temp);
s1 -= j; // 这里要 -j
j = j << 1;
}
if (s1)
{
PII temp(v1 * s1, w1 * s1);
item.push_back(temp);
}
}
for (int i = 0; i < item.size(); ++i)
for (int j = m; j >= item[i].x; --j)
f[j] = max(f[j] , f[j - item[i].x] + item[i].y);
cout << f[m];
return 0;
}