この問題は個数制限付きナップサック問題です。

素直な01ナップサックの要領の動的計画法で時間計算量 \(\mathrm{O}(S(\sum c_i ))\) などになります。

種類数である \(N\) が小さいのでこれを活かす方法を考えます。実は各種類について最大で \(c_i\) 個選べるというのは \(O(\log c_i)\) 個の商品に言い換えられます。具体的には、以下の操作を繰り替えして得られた商品を考えます。

int k = 1;
while (c[i] > 0) {
    add(w[i] * k, v[i] * k); // k個をまとめて1つの商品にする
    c[i] -= k;
    k = min(2 * k, c[i]);
}

これでよい理由は \(1,2,4,\ldots,2^k,c_i-2^{k+1}+1\) 個がそれぞれまとめられて \(1\) つの商品とされた \(k+2\) 個の商品のうち\(0\) 個以上いくつか選ぶことで必ず \(0\) から \(c_i\) 個まで選ぶ個数を網羅できるからです。(2進数で\(0\) から 2^{k+1}-1をカバーし、残りの部分を最後の一つの商品で補っている)

これで、商品の個数を \(\mathrm{O}(N\log \max c)\) 個に言い換えることができた。これに01ナップサックの動的計画法を適用すると全体で時間計算量 \(\mathrm{O}(SN\log \max c)\) で解くことができます。

bonus: \(\mathrm{O}(SN)\) でこの問題を解いてください。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, s;
    cin >> n >> s;
    vector<int> dp(s + 1, -1e9);
    dp[0] = 0;
    auto add = [&](int w, int v) -> void {
        for (int i = s; i >= w; --i) {
            if (dp[i - w] >= 0) dp[i] = max(dp[i], dp[i - w] + v);
        }
    };
    for (int i = 0; i < n; ++i) {
        int w, v, c;
        cin >> w >> v >> c;
        int k = 1;
        while (c > 0) {
            add(k * w, k * v);
            c -= k;
            k = min(2 * k, c);
        }
    }
    if (dp[s] == -(int)1e9)
        cout << -1 << endl;
    else
        cout << dp[s] << endl;
}