Overview

Given \(N\) items, select any combination such that the total cost is maximized while staying within a budget of \(K\) yen. This is a classic 0-1 knapsack problem (subset sum problem).

Analysis

Naive Approach

For each of the \(N\) items, there are 2 choices: “buy” or “don’t buy,” giving \(2^N\) total combinations. When \(N\) can be up to \(100\), \(2^{100}\) is an astronomically large number, making brute-force search completely infeasible (TLE).

Key Insight

In this problem, only “is the total cost at most \(K\)?” matters, and \(K \leq 10^4\) is relatively small. Therefore, we can use dynamic programming (DP) that tracks “can we achieve exactly \(j\) yen as the total cost?” for each \(j = 0, 1, 2, \ldots, K\).

Concrete Example

For example, with \(N = 3\), \(K = 10\), \(C = [3, 5, 7]\): - Buy nothing → total \(0\) yen ✓ - \(\{3\}\) → \(3\) yen ✓ - \(\{5\}\) → \(5\) yen ✓ - \(\{3, 5\}\) → \(8\) yen ✓ - \(\{7\}\) → \(7\) yen ✓ - \(\{3, 7\}\) → \(10\) yen ✓ ← This is the maximum - \(\{5, 7\}\) → \(12\) yen ✗ (exceeds \(K\))

Using DP, we can efficiently determine all of these.

Algorithm

We use a 0-1 knapsack-style subset sum DP.

1. DP array definition: dp[j] = “Can we select some items to make the total cost exactly \(j\) yen? (True/False)”
2. Initial state: dp[0] = True (buying nothing gives a total of \(0\) yen); all others are False
3. Transition: For each item with cost \(c\), iterate in reverse order \(j = K, K-1, \ldots, c\), and if dp[j - c] is True, set dp[j] = True
   • Reason for iterating in reverse: To prevent using the same item more than once. If we iterate forward, the effect of a single item propagates multiple times.
4. Obtaining the answer: Check \(j = K, K-1, \ldots, 0\) in order, and the first \(j\) where dp[j] is True is the answer.

Complexity

• Time complexity: \(O(N \times K)\)
  • For each of the \(N\) items, we scan all costs up to \(K\)
  • At most about \(100 \times 10^4 = 10^6\), which is sufficiently fast
• Space complexity: \(O(K)\)
  • Only a 1-dimensional DP array is used

Implementation Notes

• Reverse-order loop is crucial: By looping in descending order from \(K\) down to \(c\) with for j in range(K, c - 1, -1), we guarantee that each item is selected at most once. If we loop in ascending order (range(c, K+1)), the same item could be used multiple times (turning it into a subset sum problem with repetition), so care must be taken.

• The update rule is simply: if dp[j - c] is True, set dp[j] = True.

• Finally, by finding the largest \(j\) where dp[j] is True, we obtain the maximum total cost that does not exceed \(K\).

  Source Code

N, K = map(int, input().split())
C = list(map(int, input().split()))

dp = [False] * (K + 1)
dp[0] = True

for c in C:
    for j in range(K, c - 1, -1):
        if dp[j - c]:
            dp[j] = True

for j in range(K, -1, -1):
    if dp[j]:
        print(j)
        break

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