概要

\(N\) 個の屋台から予算 \(M\) 円以内で商品を選び、得られる満足度の合計を最大化する問題。

考察

この問題は「ナップサック問題」の一種です。各屋台の食べ物を選ぶか選ばないかという2択があり、予算制限内で満足度を最大化する必要があります。

素朴な方法として、全パターンを試すことを考えます。しかし、屋台の数 \(N\) が最大 \(15\) なので、選び方の総数は \(2^{15} = 32768\) 通りあり、これは十分小さいため全探索が可能です。

もし \(N\) がもっと大きければ、動的計画法などで効率的に解く必要がありますが、今回はビット全探索による全探索が現実的かつ簡単な解法です。

アルゴリズム

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

各屋台に対して「買う（1）」または「買わない（0）」を決めると、\(N\) 個の屋台に対する選び方は長さ \(N\) のビット列で表現できます。たとえば \(N=3\) なら、000, 001, …, 111 の \(2^3=8\) 通りの選び方が存在します。

これを整数 mask を用いて、0 から 2^N - 1 までループすることで全探索します。

各 mask に対して： - ビットが立っている場所に対応する屋台の商品を買う - 合計コストと合計満足度を計算 - コストが予算 \(M\) 以下であれば、満足度の最大値を更新

このようにして、条件を満たす中で最も高い満足度を得る選び方を見つけます。

具体例

入力例：

3 5
2 3
3 4
1 2

屋台が3個あるので、全 \(2^3=8\) 通りを調べます。

mask (2進)	選ぶ屋台	合計コスト	合計満足度
000	なし	0	0
001	1	2	3
010	2	3	4
011	1,2	5	7 ← 最大
100	3	1	2
101	1,3	3	5
110	2,3	4	6
111	1,2,3	6	9 （予算超過）

よって答えは 7 になります。

計算量

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

時間計算量は、\(2^N\) 通りの選び方それぞれに対して、\(N\) 個の屋台をチェックする必要があるためです。

実装のポイント

• ビット演算 mask & (1 << i) で、\(i\) 番目のビットが立っているか判定できる

• 各ビット列に対してコストと満足度を累積していく

• 予算オーバーの場合は無視する

• 最大値を記録する変数は最初0で初期化しておくとよい

  ソースコード

N, M = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

max_satisfaction = 0

for mask in range(1 << N):
    total_cost = 0
    total_satisfaction = 0
    for i in range(N):
        if mask & (1 << i):
            total_cost += items[i][0]
            total_satisfaction += items[i][1]
    if total_cost <= M:
        max_satisfaction = max(max_satisfaction, total_satisfaction)

print(max_satisfaction)

---

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