概要

\(N\) 個の商品からいくつか選び、ちょうど \(S\) 円になるようにして、得られる満足度の合計の最大値を求めよ。条件を満たす選び方がなければ \(-1\) を出力せよ。

考察

この問題は「ちょうど \(S\) 円になるように商品を選ぶ」という制約付きの最適化問題です。これは典型的な 部分和問題の応用 であり、「ある金額をちょうど使うときに得られる最大の満足度」を管理する必要があります。

素朴な全探索（\(2^N\) 通りを試す）は、\(N\) が最大で 3000 のため現実的ではありません（時間的に無理）。また単純な貪欲法では最適解を得られません。

そこで、動的計画法（DP） を使います。特に、「金額をキーとしたDP」を考えると効率的に解けます。

ただし、今回の問題では「1個以上の商品を選ぶ必要がある」という制約があります。そのため、DPの初期状態で「0円、0個選んで満足度0」はOKですが、最終的にそれが唯一の解になってはいけません。この点に注意が必要です。

アルゴリズム

本問題は 価格をキーとした動的計画法（ナップサック型DP）で解きます。

DPテーブルの定義

\[ dp[w] := \text{ちょうど}~w~\text{円を使って得られる最大の満足度} \]

ただし、商品は 1つ以上選ぶ必要がある ので、初期状態は以下のように設定します： - \(dp[0] = 0\)（0円使う、0個選ぶ） - それ以外の \(dp[w] = -\infty\)

更新

各商品 \((V_i, C_i)\) に対して、金額の大きい方から更新することで、同じ商品を複数回使ってしまうのを防ぎます。

更新式： $\( dp[w + C_i] = \max(dp[w + C_i],~dp[w] + V_i) \quad \text{ただし}~w + C_i \leq S \)$

ただし、\(dp[w] = -\infty\) なら更新しない（その金額は作れない）。

最終結果

最後に \(dp[S]\) の値を確認します： - もし \(dp[S] = -\infty\) なら、ちょうど \(S\) 円で買う方法がないので、\(-1\) - そうでないなら、\(dp[S]\) の値が答え

実装上の工夫

• 各商品ごとに新しいDP配列をコピーして更新（prev/curr方式）で、同じ商品を複数回選ぶのを防ぐ
• \(-\infty\) を使って「作れない金額」を表現している

計算量

• 時間計算量: \(O(N \times S)\)
• 空間計算量: \(O(S)\)

実装のポイント

• 商品を1つも選ばないケース（\(dp[0]=0\)）は初期値として許容されるが、最終的にそれが唯一の解になってはいけないことに注意

• 更新時には、常に「現在のDP」をコピーして新しいDPを作ることで、1つの商品を複数回使わないようにする

• 無限大を表す値として math.inf を使い、!= -math.inf で有効な状態かどうかを判定している

  ソースコード

import sys
import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    S = int(data[1])
    
    V = [0] * N
    C = [0] * N
    
    index = 2
    for i in range(N):
        V[i] = int(data[index])
        C[i] = int(data[index+1])
        index += 2

    # dp[i][w] := 最初のi個の商品を使って、ちょうどw円を使う時の最大満足度
    # ただし、選んだ商品が1個以上必要なので、適切に管理する
    # 初期化: -1 で初期化し、作れない場合は-1とする
    # dp[0][0] = 0 （0個使って0円使うのは可能、満足度0）
    
    prev_dp = [-math.inf] * (S + 1)
    prev_dp[0] = 0

    for i in range(N):
        curr_dp = prev_dp[:]
        v = V[i]
        c = C[i]
        for w in range(S + 1):
            if prev_dp[w] != -math.inf and w + c <= S:
                if curr_dp[w + c] < prev_dp[w] + v:
                    curr_dp[w + c] = prev_dp[w] + v
        prev_dp = curr_dp

    result = prev_dp[S]
    if result == -math.inf:
        print(-1)
    else:
        print(result)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。