Overview

A problem where you select products from \(N\) stalls within a budget of \(M\) yen to maximize the total satisfaction obtained.

Analysis

This problem is a variant of the “knapsack problem.” For each stall’s food item, there is a binary choice of whether to select it or not, and we need to maximize satisfaction within the budget constraint.

A naive approach would be to try all possible patterns. Since the number of stalls \(N\) is at most \(15\), the total number of ways to choose is \(2^{15} = 32768\), which is small enough to allow exhaustive search.

If \(N\) were much larger, we would need to solve it efficiently using dynamic programming or similar techniques, but in this case, exhaustive search using bitmask enumeration is a practical and straightforward solution.

Algorithm

We use bitmask enumeration.

For each stall, we decide either “buy (1)” or “don’t buy (0),” so the selection for \(N\) stalls can be represented as a bit string of length \(N\). For example, if \(N=3\), there are \(2^3=8\) possible selections: 000, 001, …, 111.

We perform the exhaustive search by looping an integer mask from 0 to 2^N - 1.

For each mask: - Buy the products from the stalls corresponding to the set bits - Calculate the total cost and total satisfaction - If the cost is within the budget \(M\), update the maximum satisfaction

In this way, we find the selection that yields the highest satisfaction among those satisfying the constraint.

Concrete Example

Sample input:

3 5
2 3
3 4
1 2

Since there are 3 stalls, we examine all \(2^3=8\) patterns.

mask (binary)	Selected stalls	Total cost	Total satisfaction
000	none	0	0
001	1	2	3
010	2	3	4
011	1,2	5	7 ← maximum
100	3	1	2
101	1,3	3	5
110	2,3	4	6
111	1,2,3	6	9 (exceeds budget)

Therefore, the answer is 7.

Complexity

• Time complexity: \(O(N \cdot 2^N)\)
• Space complexity: \(O(N)\)

The time complexity arises because for each of the \(2^N\) possible selections, we need to check \(N\) stalls.

Implementation Notes

• The bit operation mask & (1 << i) can be used to check whether the \(i\)-th bit is set

• For each bit string, accumulate the cost and satisfaction

• Ignore cases where the budget is exceeded

• It is recommended to initialize the variable that records the maximum value to 0

  Source Code

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)

---

This editorial was generated by qwen3-coder-480b.