概要

\(N\) 個の商品から1個以上を選び、価格の合計がちょうど \(S\) 円になるようにしたとき、満足度の合計の最大値を求める問題です。典型的な 0-1ナップサック問題 の変形です。

考察

問題の本質

この問題は「価格の合計がちょうど \(S\) になる」という制約付きで満足度を最大化する問題です。通常のナップサック問題では「価格の合計が \(S\) 以下」ですが、本問では「ちょうど \(S\)」である点が異なります。

素朴なアプローチ

全ての商品の選び方を試すと \(2^N\) 通りあります。\(N\) が最大 \(3000\) なので \(2^{3000}\) は天文学的な数であり、全探索は到底間に合いません。

動的計画法（DP）による解決

ナップサック問題と同様に、動的計画法を使います。

\(dp[j]\) を「価格の合計がちょうど \(j\) 円となるように商品を選んだときの、満足度の最大値」と定義します。達成不可能な場合は \(-1\) とします。

初期値は \(dp[0] = 0\)（何も選ばなければ価格は \(0\) 円、満足度も \(0\)）、それ以外は \(dp[j] = -1\) です。

具体例: \(N=3\), \(S=5\), 商品が \((V, C) = (3, 2), (4, 3), (1, 2)\) の場合

• 商品1 \((V=3, C=2)\) を処理後: \(dp[2] = 3\)
• 商品2 \((V=4, C=3)\) を処理後: \(dp[2] = 3\), \(dp[3] = 4\), \(dp[5] = 7\)
• 商品3 \((V=1, C=2)\) を処理後: \(dp[5] = \max(7, dp[3]+1) = \max(7, 5) = 7\)

答えは \(dp[5] = 7\) です。

アルゴリズム

0-1ナップサック問題のDP（1次元配列版）を用います。

1. \(dp[0] = 0\), \(dp[1] = dp[2] = \cdots = dp[S] = -1\) と初期化する。
2. 各商品 \((V_i, C_i)\) について、\(j = S, S-1, \ldots, C_i\) の順（逆順）に以下を行う：
   • \(dp[j - C_i] \geq 0\) ならば、\(dp[j] = \max(dp[j],\ dp[j - C_i] + V_i)\) と更新する。
3. 最終的に \(dp[S]\) が答え。\(dp[S] = -1\) なら達成不可能。

逆順に走査する理由: 同じ商品を2回以上使ってしまうのを防ぐためです。昇順に走査すると、ある商品で更新された値をさらに同じ商品で更新してしまう可能性があります。逆順にすることで、各商品は最大1回しか使われません。

計算量

• 時間計算量: \(O(N \times S)\)（各商品について \(S\) 以下の各金額を走査）
  • 最大で \(3000 \times 10000 = 3 \times 10^7\) 程度で十分高速です。
• 空間計算量: \(O(S)\)（1次元のDP配列）

実装のポイント

• 初期値の設定: \(dp[0] = 0\) のみを達成可能とし、他は \(-1\)（達成不可能）とする。これにより「ちょうど \(j\) 円」という条件を正しく扱える。通常のナップサック問題（\(S\) 円以下）では全て \(0\) で初期化しますが、本問では区別が必要です。

• 逆順ループ: for j in range(S, c - 1, -1) により、各商品を最大1個しか選ばないことを保証する。

• \(dp[j-c] \geq 0\) のチェック: 遷移元が達成可能な状態かどうかを確認してから更新する。達成不可能な状態（\(-1\)）から遷移しないようにする。

  ソースコード

def main():
    N, S = map(int, input().split())
    items = []
    for _ in range(N):
        v, c = map(int, input().split())
        items.append((v, c))
    
    # dp[j] = maximum satisfaction when total cost is exactly j, -1 if not achievable
    dp = [-1] * (S + 1)
    dp[0] = 0
    
    for v, c in items:
        # Traverse in reverse to ensure each item is used at most once
        for j in range(S, c - 1, -1):
            if dp[j - c] >= 0:
                dp[j] = max(dp[j], dp[j - c] + v)
    
    print(dp[S])

main()

---

この解説は claude4.6opus-thinking によって生成されました。