Overview

Given \(N\) items, determine whether it is possible to select some of them so that their total price is exactly \(S\) yen, and if possible, find the minimum number of items to select.

Analysis

• Each item has two choices: select or not select, and the same item cannot be selected more than once (0/1 selection).
• The goal is not just “whether we can make a total of \(S\)” but also the minimum number of items when possible, so a simple reachability check (true/false) is insufficient.

Why a naive approach is difficult

• Trying all subsets results in \(2^N\) possibilities, which is infeasible for \(N \le 100\).
• Using DP to determine “whether we can make a total of \(S\)” is a well-known technique, but this time we also need the “minimum number of items.”

Solution Strategy

• Manage “the minimum number of items needed to make a total price of \(s\)” using DP.
• By processing each item in order and reflecting “the case where this item is used,” we can simultaneously find the minimum number of items.

For example, when \(S=7\) and the items are \([2,3,5]\): - \(7=2+5\) requires 2 items - \(7=2+3+?\) cannot be formed
So the answer is 2. We update the “minimum number of items” through DP in this manner.

Algorithm

We use a 0/1 knapsack-style DP (minimum count version).

• Define array \(dp[s]\) as “the minimum number of items needed to make a total of \(s\) yen”
• Initialization:
  • \(dp[0]=0\) (0 yen can be made by selecting nothing)
  • All others are unreachable, so \(dp[s]=\infty\)
• For each item price \(a\), update as follows:
  • Move \(s\) from the larger side in decreasing order: \(S, S-1, \dots, a\),
  • If \(dp[s-a]\) is reachable, set \(dp[s] = \min(dp[s],\ dp[s-a]+1)\)

Iterating in decreasing order is crucial — this guarantees that “each item is used at most once (0/1).” If we iterate in increasing order, the same item could be used multiple times (which corresponds to the unbounded version of the problem).

Finally, - If \(dp[S]\) remains \(\infty\), it is impossible, so output \(-1\) - Otherwise, output \(dp[S]\)

Complexity

• Time complexity: \(O(NS)\) (updating \(0 \sim S\) for each item)
• Space complexity: \(O(S)\) (only a one-dimensional DP array)

Implementation Notes

• Decreasing order loop (for s in range(S, a-1, -1)) prevents the mistake of using the same item multiple times.

• Use a sufficiently large INF to represent unreachable states, and check whether dp[S] >= INF at the end.

• Items with \(a > S\) cannot contribute to a total of \(S\), so they can be skipped (this also improves performance).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, S = data[0], data[1]
    A = data[2:2+N]

    INF = 10**9
    dp = [INF] * (S + 1)
    dp[0] = 0

    for a in A:
        if a > S:
            continue
        for s in range(S, a - 1, -1):
            if dp[s - a] + 1 < dp[s]:
                dp[s] = dp[s - a] + 1

    print(-1 if dp[S] >= INF else dp[S])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.