多重背包原理

for (int i = 1;i <= n;++i) {
  for (int j = 0;j <= m;++j) {
    for (int k = 0;k * v[i] <= j && k <= s[i];++k) {
      f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    }
  }
}

int cnt = 0;
for (int i = 1;i <= n;++i) {
   int a, b, s;
   cin >> a >> b >> s;
   int k = 1;
   while (k <= s) {
    cnt++;
    v[cnt] = a * k;
    w[cnt] = b * k;
    s -= k;
    k *= 2;
   }
   if (s > 0) {
    ++cnt;
    v[cnt] = a * s;
    w[cnt] = b * s;
   }
}
n = cnt;
for (int i = 1; i <= n;++i) {
   for (int j = m;j >= v[i];--j) {
    f[j] = max(f[j], f[j - v[i]] + w[i]);
   }
}