显示代码纯文本
#include <iostream>
#include <cstdio>
#define MAXN 100000
//#define DEBUG
using namespace std;
int w[MAXN],v[MAXN],tot = 0;
int f[MAXN];
int main()
{
#ifndef DEBUG
freopen("treasure.in","r",stdin);
freopen("treasure.out","w",stdout);
#endif // DEBUG
int n,W;
cin >> n >> W;
for(int i = 1;i <= n;i++)
{
int a,b,c;
cin >> a >> b >> c;
int t = 1;
while(t <= c)
{
v[++tot] = a*t;
w[tot] = b*t;
c -= t;
t <<= 1;
}
if(c)
{
v[++tot] = a*c;
w[tot] = b*c;
}
}
for(int i = 1;i <= tot;i++)
{
for(int j = W;j >= w[i];j--)
{
f[j] = max(f[j],f[j-w[i]] + v[i]);
}
}
cout << f[W];
return 0;
}