概要

商品の価格の合計がちょうど \(S\) 円となるように商品を選び、その中で満足度の合計の最大値を求める問題です。そのような選び方が存在しない場合は \(-1\) を出力します。

考察

この問題は、各商品を最大1個まで選ぶことができる「ナップサック問題」の一種ですが、通常のナップサック問題とは異なり、価格の合計がちょうど \(S\) 円になるように選ぶ必要があります。素朴な全探索では \(2^N\) 通り試す必要があり、\(N\) が最大3000なので現実的ではありません。

動的計画法を用いることで効率的に解くことができます。dp[j]を「価格の合計がちょうど j 円となる選び方における満足度の合計の最大値」と定義します。ただし、j 円ちょうどにする選び方が存在しない場合は負の無限大などの特別な値で管理します。

アルゴリズム

1. dp[0] = 0（0円ちょうどは何も選ばない場合で満足度0）と初期化し、その他は負の無限大（\(\mathrm{INF}\)）で初期化します。
2. 各商品について、価格 \(c_i\)、満足度 \(v_i\) で、金額 \(S\) から \(c_i\) まで逆順にループします。
3. dp[j - c_i] が \(\mathrm{INF}\) でない（つまり j - c_i 円ちょうどにする選び方が存在する）場合、dp[j] を dp[j - c_i] + v_i で更新できるか確認します。
4. 全ての商品について処理した後、dp[S] が \(\mathrm{INF}\) ならば -1 を、そうでなければ dp[S] を出力します。

この方法は「0-1ナップサック問題」のちょうどピッタリ版と呼ばれるものです。逆順にループすることで、同じ商品を複数回選ばないようにしています。

計算量

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

実装のポイント

• 初期化時に dp[0] = 0、それ以外は十分に小さい値（\(\mathrm{INF}\)）に設定する

• ループは金額が大きい方から小さい方へ処理する（同じ商品を重複して選ばないため）

• dp[S] が初期値のままなら -1 を出力する

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    S = int(data[1])
    V = []
    C = []
    index = 2
    for i in range(n):
        v = int(data[index])
        c = int(data[index+1])
        index += 2
        V.append(v)
        C.append(c)
    
    INF = -10**18
    dp = [INF] * (S+1)
    dp[0] = 0
    
    for i in range(n):
        c_i = C[i]
        v_i = V[i]
        for j in range(S, c_i-1, -1):
            if dp[j - c_i] != INF:
                if dp[j] < dp[j - c_i] + v_i:
                    dp[j] = dp[j - c_i] + v_i
    
    if dp[S] == INF:
        print(-1)
    else:
        print(dp[S])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。