Overview

Given \(N\) food stalls, select foods such that the total cost does not exceed the budget of \(M\) yen, and maximize the total satisfaction. This is a type of the so-called 0-1 knapsack problem.

Analysis

• For each stall, there are 2 choices: “buy” or “don’t buy”, so there are \(2^N\) possible selections in total.
• Since \(N\) is at most 15, we have \(2^{15} = 32768\) possibilities. This is small enough that enumerating all combinations will easily fit within the time limit.
• If \(N\) were large (e.g., \(N = 100\)), \(2^{100}\) would be an astronomically large number, making full enumeration impossible, and techniques like dynamic programming (DP) would be required. However, with the constraint \(N \leq 15\) in this problem, full enumeration (bitmask search) is sufficient.

Algorithm

We use bitmask enumeration.

Number the \(N\) stalls from \(0\) to \(N-1\). We iterate an integer mask from \(0\) to \(2^N - 1\), where each bit of mask represents “whether or not to buy food from that stall.”

Concrete example (when \(N = 3\)):

For each mask, we do the following:

1. Compute the total cost cost and the total satisfaction sat of the stalls whose corresponding bits are set.
2. If cost does not exceed the budget \(M\), check whether sat exceeds the current maximum best, and update it if so.

The value of best after examining all values of mask is the answer.

Complexity

• Time complexity: \(O(2^N \times N)\)
  • For each of the \(2^N\) combinations, we scan all \(N\) stalls to compute the cost and satisfaction.
  • When \(N = 15\), this is about \(2^{15} \times 15 = 491520\) operations, which is fast enough.
• Space complexity: \(O(N)\)
  • Only the arrays storing the stall information are needed.

Implementation Notes

• mask & (1 << i) checks whether the \(i\)-th bit of mask is set. If true, it means we buy food from stall \(i\).

• The initial value of best is set to \(0\). Since the satisfaction when buying nothing (mask = 0) is \(0\), this serves as the minimum guarantee.

• 1 << N is a Python bit shift operation meaning \(2^N\). range(1 << N) enumerates all integers from \(0\) to \(2^N - 1\).

  Source Code

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)

This editorial was generated by claude4.6opus-thinking.