Overview

This is a problem of maximizing the total price among combinations of products that can be purchased within a budget of \(K\) yen.

Analysis

This problem can be considered as a variant of the “Knapsack Problem.”
Each product has only a “price,” and there is a binary choice of whether to select it or not. The goal is to select products such that the total price does not exceed \(K\), and to maximize that total.

A naive approach would be to try all subsets of products (brute force), but since the number of products \(N\) can be up to 100, this would result in \(2^{100}\) combinations, which is not feasible (TLE).

Therefore, we consider using Dynamic Programming (DP).
In this problem, it can be efficiently solved by creating a DP table that tracks the boolean value of “Can we spend exactly \(w\) yen?” That is, if dp[w] = True, it means there exists a way to select products whose total is exactly \(w\) yen.

In the initial state, we set dp[0] = True (if we buy nothing, the cost is 0 yen), and then we examine each product one by one, updating the reachable amounts using that product.

When updating, it is important to note that in order to avoid using the same product multiple times, we must iterate from larger amounts to smaller amounts (a classic DP technique).

Finally, the answer is the maximum \(w\) such that dp[w] == True (where \(w \leq K\)).

Example

For example, given the following input:

N=3, K=5
C = [2, 3, 4]

• Initially: dp = [True, False, False, False, False, False]
• Process product with price 2 → dp = [True, False, True, False, False, False]
• Process product with price 3 → dp = [True, False, True, True, False, True]
• Process product with price 4 → dp = [True, False, True, True, True, True]

The maximum index with True among these is 5, so the answer is 5 yen.

Algorithm

This problem can be solved as an application of the subset sum problem.

• Manage a DP array dp[w] as a boolean value representing “Can we make the total amount exactly \(w\) yen?”
• Initial state: dp[0] = True
• For each product price \(c\), iterate in reverse order from \(K\) yen down to \(c\) yen, and perform the transition:
  • if dp[w - c]: dp[w] = True
• Finally, find the maximum \(w \leq K\) such that dp[w] == True.

Complexity

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

Implementation Notes

• The DP table must always be updated from larger amounts to smaller amounts (to avoid using the same product multiple times).

• A 1-dimensional boolean array is sufficient for the DP table.

• A final step is needed to find the maximum \(w\) such that dp[w] == True.

  Source Code

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

# dp[i][w] := i番目までの商品を使って、ちょうどw円になるか？
dp = [False] * (K + 1)
dp[0] = True

for c in C:
    # 後ろから更新することで、同じ商品を複数回使わないようにする
    for w in range(K, c - 1, -1):
        if dp[w - c]:
            dp[w] = True

# dp[w] == True となる最大の w を求める
max_total = 0
for w in range(K + 1):
    if dp[w]:
        max_total = w

print(max_total)

---

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