概要

この問題は、商品の個数に制限がある状況で、重さの合計がちょうど \(S\) になるように商品を選び、満足度の合計を最大化する「個数制限付きナップサック問題（Bounded Knapsack Problem）」です。

考察

素朴なアプローチとその限界

最も単純な動的計画法（DP）の設計として、以下のような状態を考えます。 - \(dp[i][j] :=\) \(i\) 番目の商品まで見て、重さの合計がちょうど \(j\) のときの満足度の最大値

各商品 \(i\) について、購入する個数を \(0\) から \(c_i\) まで試すと、DPの遷移は次のようになります。 $\(dp[i][j] = \max_{0 \le k \le c_i} (dp[i-1][j - k \cdot w_i] + k \cdot v_i)\)$

しかし、この方法では時間計算量が \(O(N \cdot S \cdot \max(c_i))\) となります。 制約を見ると \(N \le 100\), \(S \le 30000\), \(c_i \le 10^5\) であるため、最悪の場合の計算回数は \(100 \times 30000 \times 10^5 = 3 \times 10^{11}\) 回となり、実行時間制限に到底間に合いません（TLEとなります）。

解決策：個数の「2進数分解」

個数制限付きナップサック問題を高速に解くための強力なテクニックが「2進数分解（Binary Grouping）」です。

例えば、ある商品を「最大 \(13\) 個まで買える」とします。このとき、愚直に \(0, 1, 2, \dots, 13\) 個選ぶ遷移を考える代わりに、商品を以下の個数の「束（グループ）」に分割します。 - \(1\) 個の束 - \(2\) 個の束 - \(4\) 個の束 - \(6\) 個の束（残りの分：\(13 - (1 + 2 + 4) = 6\)）

これら \(1, 2, 4, 6\) の束は、「選ぶ（1）」か「選ばない（0）」かの2択として扱います。 不思議なことに、これらの束を組み合わせる（01ナップサック問題として解く）だけで、\(0\) から \(13\) までの任意の個数を過不足なく作り出すことができます。 - \(3\) 個作りたい \(\to\) \(1\) 個の束 と \(2\) 個の束 を選ぶ - \(5\) 個作りたい \(\to\) \(1\) 個の束 と \(4\) 個の束 を選ぶ - \(11\) 個作りたい \(\to\) \(1\) 個の束, \(4\) 個の束, \(6\) 個の束 を選ぶ

一般に、個数 \(c\) を \(1, 2, 4, 8, \dots, 2^k\) および残りの数に分解すると、分割後の束の数は \(O(\log c)\) 個になります。 今回の制約では \(c_i \le 10^5\) ですが、\(\log_2(10^5) \approx 17\) なので、1つの商品を高々 \(17\) 個の独立した商品に変換できます。 これにより、商品数を最大 \(100 \times 17 = 1700\) 個程度に抑えた「01ナップサック問題」に帰着させることができます。

---

アルゴリズム

1. 個数の上限カット（枝刈り） 重さ \(w_i\) の商品を、目標の重さ \(S\) を超えて購入することはありません。したがって、各商品の個数制限 \(c_i\) はあらかじめ \(\min(c_i, \lfloor S / w_i \rfloor)\) に制限して差し支えありません。これにより、不要な分解を避けてさらに高速化できます。

2. 2進数分解による商品リストの作成 各商品 \((w_i, v_i, c_i)\) について、個数 \(c_i\) を \(1, 2, 4, \dots\) と2進数的に分割し、新しい商品（重さ：\(\text{個数} \times w_i\)、満足度：\(\text{個数} \times v_i\)）を作成してリスト items に追加します。

3. 1次元DPによる01ナップサック問題の解決 「ちょうど \(S\) グラム」にする必要があるため、DP配列 dp を \(-1\)（不可能な状態）で初期化し、dp[0] = 0 とします。 作成した items の各商品 \((w, v)\) について、DP配列を後ろ（\(S\) から \(w\)）から更新します。 $\(dp[j] = \max(dp[j], dp[j - w] + v) \quad (\text{ただし } dp[j-w] \neq -1)\)$

4. 答えの出力 最終的な答えは dp[S] に格納されます。ちょうど \(S\) グラムにすることが不可能な場合は、初期値の -1 がそのまま出力されます。

---

計算量

時間計算量: \(O(S \sum_{i=1}^N \log(\min(c_i, \lfloor S / w_i \rfloor)))\)

各商品 \(i\) の個数は高々 \(\log(c_i)\) 個のグループに分割されます。 分割後の総商品数を \(M\) とすると、最悪の場合でも \(M \le 100 \times \log_2(30000) \approx 1500\) です。 01ナップサック問題の計算量は \(O(M \cdot S)\) となるため、全体の計算回数は最大でも \(1500 \times 30000 \approx 4.5 \times 10^7\) 回となり、実行時間制限（通常2秒）以内に余裕で間に合います。

空間計算量: \(O(S + N \log(\min(c_i, \lfloor S / w_i \rfloor)))\)

DP配列に必要なメモリは \(S + 1\) のサイズです。また、分割後の商品を格納するリストのサイズは最大で \(M\) です。 \(S \le 30000, M \le 1500\) であるため、メモリ使用量は数メガバイト程度に収まり、非常に軽量です。

---

実装のポイント

• DPの更新方向 1次元配列で01ナップサック問題を解く際、同じ商品を重複して選ばないようにするため、重さのループは必ず大きい方から小さい方へ（逆順に）回す必要があります。

  for j in range(total_w, w - 1, -1):
  

• 無駄な遷移の省略（total_w による最適化） これまでに処理した商品の重さの合計 total_w を記録しておき、DPを更新する範囲を total_w までに制限しています。これにより、まだ到達不可能な大きな重量に対する無駄なループをスキップでき、定数倍の高速化に貢献しています。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    S = int(data[1])

    items = []
    idx = 2
    for _ in range(N):
        w = int(data[idx])
        v = int(data[idx + 1])
        c = int(data[idx + 2])
        idx += 3

        c = min(c, S // w)
        if c == 0:
            continue

        k = 1
        while c > 0:
            num = min(k, c)
            items.append((num * w, num * v))
            c -= num
            k *= 2

    dp = [-1] * (S + 1)
    dp[0] = 0

    total_w = 0
    for w, v in items:
        total_w += w
        if total_w > S:
            total_w = S
        for j in range(total_w, w - 1, -1):
            prev = dp[j - w]
            if prev >= 0:
                val = prev + v
                if val > dp[j]:
                    dp[j] = val

    print(dp[S])


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。