Overview

This problem is a knapsack problem where you select a combination of food items from stalls that can be purchased within a budget of \(M\) yen, maximizing the total satisfaction.

Analysis

Since the number of stalls \(N\) is at most 15, a brute-force search (\(2^{15} = 32768\) combinations) is also feasible. However, since the budget \(M\) can be up to \(10^4\), which is relatively large, we can solve it efficiently using dynamic programming (DP). By using DP, which is the classic approach for the knapsack problem, we can compute the maximum satisfaction for each amount and ultimately find the maximum value.

Algorithm

Using dynamic programming, we define dp[j] as “the maximum satisfaction obtainable within a budget of j yen.” For each stall’s food item, if the amount j is at least the price \(T_i\) of that item, we update dp[j] to the larger of “the current dp[j]” and “dp[j - T_i] + P_i.” By performing this update in reverse order (from larger to smaller j), we prevent selecting the same food item more than once. Finally, the maximum value among dp[0] through dp[M] is the answer.

Complexity

• Time complexity: \(O(N \cdot M)\)
• Space complexity: \(O(M)\)

Implementation Notes

• The DP array has size \(M+1\), initialized to 0.

• For each stall, we iterate j from \(M\) down to \(T_i\) while updating, which prevents selecting the same food item multiple times.

• Finally, output the maximum value in the dp array.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    M = int(data[1])
    T = []
    P = []
    index = 2
    for i in range(n):
        T.append(int(data[index]))
        P.append(int(data[index+1]))
        index += 2
        
    dp = [0] * (M + 1)
    
    for i in range(n):
        t = T[i]
        p = P[i]
        for j in range(M, t - 1, -1):
            if dp[j] < dp[j - t] + p:
                dp[j] = dp[j - t] + p
                
    print(max(dp))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.