概要

\(N\) 個の屋台から、合計金額が所持金 \(M\) 円以下となるように食べ物を選び、満足度の合計を最大化する問題です。いわゆる 0-1ナップサック問題 の一種です。

考察

• 各屋台について「買う」か「買わない」の2択があるので、選び方は全部で \(2^N\) 通りあります。
• \(N\) が最大15なので、\(2^{15} = 32768\) 通りです。これは十分小さいため、すべての組み合わせを全列挙しても余裕で間に合います。
• もし \(N\) が大きい場合（例えば \(N = 100\) など）、\(2^{100}\) は天文学的な数になるため全列挙は不可能で、動的計画法（DP）などが必要になります。しかし今回は \(N \leq 15\) という制約があるため、全列挙（ビット全探索）で十分です。

アルゴリズム

ビット全探索を用います。

\(N\) 個の屋台に \(0\) から \(N-1\) までの番号を振ります。整数 mask を \(0\) から \(2^N - 1\) まで動かし、mask の各ビットが「その屋台の食べ物を買うかどうか」を表すと考えます。

具体例（\(N = 3\) の場合）：

各 mask に対して以下を行います：

1. ビットが立っている屋台の 値段の合計 cost と 満足度の合計 sat を計算する。
2. cost が所持金 \(M\) 以下であれば、sat が今までの最大値 best を超えるか確認し、超えていれば更新する。

すべての mask を調べた後の best が答えです。

計算量

• 時間計算量: \(O(2^N \times N)\)
  • \(2^N\) 通りの組み合わせそれぞれについて、\(N\) 個の屋台を走査してコストと満足度を計算します。
  • \(N = 15\) のとき、\(2^{15} \times 15 = 491520\) 回程度の演算なので十分高速です。
• 空間計算量: \(O(N)\)
  • 屋台の情報を格納する配列の分のみ必要です。

実装のポイント

• mask & (1 << i) で mask の第 \(i\) ビットが立っているかを判定します。これが真なら屋台 \(i\) の食べ物を購入することを意味します。

• best の初期値は \(0\) にしておきます。何も買わない場合（mask = 0）の満足度が \(0\) なので、これが最低保証となります。

• 1 << N は \(2^N\) を意味する Python のビットシフト演算です。range(1 << N) で \(0\) から \(2^N - 1\) までの整数を列挙できます。

  ソースコード

N, M = map(int, input().split())
items = []
for _ in range(N):
    t, p = map(int, input().split())
    items.append((t, p))

best = 0
for mask in range(1 << N):
    cost = 0
    sat = 0
    for i in range(N):
        if mask & (1 << i):
            cost += items[i][0]
            sat += items[i][1]
    if cost <= M and sat > best:
        best = sat

print(best)

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