Overview

Given \(N\) items, we want to select some of them so that the total price is exactly \(S\) yen. If such a selection exists, find the minimum number of items; otherwise, output \(-1\). This can be solved using dynamic programming (DP) as a variant of the 0/1 knapsack problem.

Analysis

Naive Approach (Exhaustive Search)

Since each of the \(N\) items can either be “selected” or “not selected,” an exhaustive search would examine \(2^N\) combinations. When \(N = 100\), this gives \(2^{100} \approx 10^{30}\), which is far too slow.

Key Insight

This problem requires us to simultaneously determine “whether the total amount can be exactly \(S\)” and “if so, what is the minimum number of items.” The important observations are:

• Each item can be selected at most once (0/1 knapsack)
• The target amount \(S\) is at most \(10000\), which is relatively small

This allows us to efficiently use DP with the amount as the state.

DP Definition

Define \(dp[j]\) = “the minimum number of items selected such that the total price is exactly \(j\) yen.”

The initial values are \(dp[0] = 0\) (selecting nothing gives a total of \(0\) yen with \(0\) items), and all others are \(\infty\) (not yet achievable).

Transition

When considering item \(i\) (with price \(A_i\)), for each amount \(j\):

\[dp[j] = \min(dp[j],\ dp[j - A_i] + 1)\]

This means “take a way to make \(j - A_i\) yen and add item \(i\) to make \(j\) yen.”

Reason for Reverse-Order Loop

To avoid using the same item more than once, we loop \(j\) in reverse order from \(S\) down to \(A_i\). If we looped in ascending order, we would use an already-updated \(dp[j - A_i]\), effectively selecting the same item multiple times.

Algorithm

1. Initialize \(dp[0] = 0\) and \(dp[1], dp[2], \ldots, dp[S] = \infty\).
2. For each item \(i = 0, 1, \ldots, N-1\):
   • Loop \(j = S, S-1, \ldots, A_i\) in that order, updating \(dp[j] = \min(dp[j],\ dp[j - A_i] + 1)\).
3. At the end, if \(dp[S]\) is still \(\infty\), output \(-1\); otherwise, output \(dp[S]\).

Worked Example

For \(N = 3,\ S = 7,\ A = [3, 4, 5]\):

• Initial: \(dp = [0, \infty, \infty, \infty, \infty, \infty, \infty, \infty]\)
• After processing item 1 (price 3): \(dp[3] = 1\)
• After processing item 2 (price 4): \(dp[4] = 1,\ dp[7] = 2\)
• After processing item 3 (price 5): \(dp[5] = 1,\ dp[8]\) is out of range so no change

Result: \(dp[7] = 2\) (select items 1 and 2)

Complexity

• Time complexity: \(O(N \times S)\) — for each item, we loop up to amount \(S\)
• Space complexity: \(O(S)\) — only a 1-dimensional DP array is used

Since \(N \leq 100,\ S \leq 10000\), the maximum number of operations is about \(100 \times 10000 = 10^6\), which runs sufficiently fast.

Implementation Notes

• Forgetting the reverse-order loop will cause the same item to be used multiple times (turning it into an unbounded knapsack problem), so be careful.

• Using float('inf') as the initial DP value naturally represents the state “this amount has not been achieved yet.”

• At the end, checking whether \(dp[S]\) is \(\infty\) simultaneously handles both the feasibility check and the output of the minimum number of items.

  Source Code

def solve():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    
    # dp[j] = minimum number of items to make sum exactly j
    INF = float('inf')
    dp = [INF] * (S + 1)
    dp[0] = 0
    
    for i in range(N):
        # Traverse in reverse to ensure each item is used at most once (0/1 knapsack)
        for j in range(S, A[i] - 1, -1):
            if dp[j - A[i]] + 1 < dp[j]:
                dp[j] = dp[j - A[i]] + 1
    
    print(dp[S] if dp[S] != INF else -1)

solve()

---

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