概要

各屋台の食べ物を「買う／買わない」で選び、合計金額が \(M\) 円以下になる範囲で満足度合計を最大化する問題です。典型的な 0/1 ナップサック問題として解けます。

考察

• 各屋台は高々1回しか買えないため、選択は「0/1」（買うか買わないか）です。
• 目的は「合計金額 \(\le M\)」の制約下で「満足度の合計最大」なので、これはそのまま 0/1 ナップサックの定式化になります。

素朴な考え方として、 - 貪欲法（例：満足度/価格が高い順に買う）は一般に正しくありません。
例えば \(M=10\)、(価格,満足度) が \((6,9),(5,8),(5,8)\) のとき、比率の高い \((6,9)\) を選ぶと残り4円で何も買えず満足度9ですが、\((5,8)+(5,8)\) なら満足度16でより良いです。 - 全探索（全ての組合せを試す）は \(2^N\) 通りです。今回は \(N \le 15\) なので理論上は間に合いますが、一般的・確実に解く方法として DP（動的計画法）を使うのが定石ですし、\(M \le 10^4\) なので \(O(NM)\) のDPが十分高速です。

そこで「今まで見た屋台だけを使って、ある金額までで得られる最大満足度」をDPで管理します。

アルゴリズム

DP配列 dp[w] を次のように定義します。

• dp[w] = 「（これまでに処理した屋台の中から選んで）合計金額がちょうど \(w\) 円になるように買ったときの満足度の最大値（不可能なら0のまま）」
  ※本コードでは dp[w-1] から dp[w] への伝播をしないため、“\(\le w\)” ではなく “ちょうど \(w\)” 寄りの状態になります。そのため最後に max(dp) を取って「\(\le M\)」の最大を回収します。

初期状態は何も買わないので dp[*]=0 です。

各アイテム（価格 \(t\), 満足度 \(p\)）について、次を行います：

• 予算 w を \(M\) から \(t\) まで 逆順に動かし、
  • dp[w] = max(dp[w], dp[w-t] + p)

逆順に回す理由： - 順方向（小さい w から）に更新すると、同じアイテムを「同じ周回内で2回使う」ような遷移が起きてしまい、0/1（各アイテム高々1回）ではなく無制限に近い挙動になります。 - 逆順なら、dp[w-t] は「このアイテムをまだ使っていない段階の値」を参照でき、各アイテムが高々1回だけ使われます。

最後に、金額が \(0 \sim M\) のどれでも良いので、 - 答えは max(dp)（合計金額 \(\le M\) を満たす中で最大満足度）

計算量

• 時間計算量: \(O(NM)\)
  （各アイテムごとに \(w=0..M\) を1回なめるため）
• 空間計算量: \(O(M)\)
  （長さ \(M+1\) の1次元DP配列）

実装のポイント

• 更新ループは必ず for w in range(M, t - 1, -1): のように 逆順にする（0/1ナップサックの重要ポイント）。

• dp[w] が「ちょうど \(w\) 円」の状態を主に表す形なので、最終的に dp[M] ではなく max(dp) を出力して「\(\le M\)」の最大値を拾う。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]  # (T, P)

    dp = [0] * (M + 1)
    for t, p in items:
        for w in range(M, t - 1, -1):
            cand = dp[w - t] + p
            if cand > dp[w]:
                dp[w] = cand

    print(max(dp))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。