概要

\(N\) 個の商品から、価格の合計がちょうど \(S\) 円になるように選んだときの、満足度の合計の最大値を求める問題です。

考察

商品の選び方を全探索すると \(2^N\) 通りとなり、制約の \(N \leq 3000\) では制限時間に間に合いません（TLE）。 この問題は、有名な「ナップサック問題」のバリエーションであり、動的計画法（DP）を用いることで効率的に解くことができます。

通常のナップサック問題は「金額（重さ）の合計が \(S\) 以下」という条件で最大値を求めますが、今回は「金額の合計が ちょうど \(S\) 円」という条件になっています。そのため、「ちょうどその金額になる選び方が存在するかどうか」を区別しながら最大値を計算していく必要があります。

アルゴリズム

1次元配列を用いた動的計画法（DP）で解き進めます。

dp[j] を「価格の合計がちょうど \(j\) 円になるときの、満足度の合計の最大値」と定義します。

1. 初期化 まだ商品を1つも見ていない状態では、価格の合計が \(0\) 円のときの満足度は \(0\) です。それ以外の金額は作ることができないため、到達不可能であることを示す -1 で初期化します。 - dp[0] = 0 - dp[j] = -1 \((1 \leq j \leq S)\)

2. 遷移（DPの更新） 各商品（満足度 \(V_i\)、価格 \(C_i\)）について、金額 \(j\) を大きい方から小さい方へ調べていき、以下のように更新します。 - もし dp[j - C_i] が -1 でない（つまり、価格の合計を \(j - C_i\) 円にする方法が既に存在する）なら、 - dp[j] = max(dp[j], dp[j - C_i] + V_i) として最大値を更新します。

3. 答えの出力 すべての商品について更新を終えた後の dp[S] が求める答えになります。もし dp[S] が -1 のままなら、ちょうど \(S\) 円になる選び方が存在しなかったということなので、そのまま -1 を出力します。

計算量

• 時間計算量: \(O(NS)\) 商品の数 \(N\) と目標金額 \(S\) の積に比例する回数のループが回ります。最大で \(3000 \times 10000 = 3 \times 10^7\) 回程度の計算となり、実行時間制限に十分間に合います。
• 空間計算量: \(O(S)\) 長さ \(S+1\) の1次元配列を1つ持つだけで済むため、メモリも非常に少なく抑えられます。

実装のポイント

• 1次元配列での更新順序: 状態の更新に1次元配列を使う場合、内側のループは必ず 大きい金額から小さい金額へ（逆順に） 回してください。小さい金額から回してしまうと、同じ商品を複数回購入してしまうことになり、正しい答えが得られません。

• 定数倍高速化: 正解コードでは max_w という変数を使って「現在までに達成可能な最大の金額」を管理しています。これにより、内側のループの開始位置を常に \(S\) から始めるのではなく、min(S, max_w + c) に制限することができ、無駄なループを減らして実行速度をさらに向上させています。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    S = int(data[1])
    
    dp = [-1] * (S + 1)
    dp[0] = 0
    
    max_w = 0
    idx = 2
    for _ in range(N):
        v = int(data[idx])
        c = int(data[idx+1])
        idx += 2
        
        limit = S if max_w + c > S else max_w + c
        for j in range(limit, c - 1, -1):
            prev = dp[j - c]
            if prev != -1:
                cand = prev + v
                if dp[j] < cand:
                    dp[j] = cand
        if max_w < limit:
            max_w = limit
            
    print(dp[S])

if __name__ == '__main__':
    solve()

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