二进制优化
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX_N = 12000, MAX_V = 2000;
int f[MAX_V];
int N, V;
int vv[MAX_N], ww[MAX_N];
int main()
{
cin >> N >> V;
int idx = 1;
for (int i = 0; i < N; i ++) {
int v, w, s;
cin >> v >> w >> s;
int base = 1;
while(s > base) {
s -= base;
vv[idx] = base * v;
ww[idx ++] = base * w;
base <<= 1;
}
if (s) {
vv[idx] = s * v;
ww[idx ++] = s * w;
}
}
for (int i = 1; i <= idx; i ++) {
for (int j = V; j >= vv[i]; j --) {
f[j] = max(f[j], f[j - vv[i]] + ww[i]);
}
}
cout << f[V];
return 0;
}