Overview

Given \(N\) items, select some of them so that their total price is exactly \(S\) yen, and find the minimum number of items to select. If it is impossible, output \(-1\).

Analysis

This problem is an optimization problem: “Among all subsets whose total equals \(S\) yen, find the one with the minimum number of elements.”

A naive approach would be to try all combinations (subsets), which gives \(2^N\) possibilities. With the constraint \(N=100\), this is not feasible (TLE). Also, greedy approaches such as simply selecting items in descending order of price do not always yield the optimal solution.

For problems of the form “Can we make a certain value (total price)?”, dynamic programming (DP) is an effective technique.

In particular, by using a DP table that tracks “the minimum number of items needed to make exactly j yen using items up to the i-th one”, the answer is stored in \(dp[N][S]\) at the end.

As the initial state, set \(dp[0][0] = 0\) (0 items can make 0 yen), and all other values to infinity (unachievable).

Algorithm

We use dynamic programming (DP) and process as follows:

• State definition:

  • \(dp[i][j]\) := the minimum number of items needed to make a total of exactly \(j\) yen using items up to the \(i\)-th one (if unachievable, \(\infty\))

• Initialization:

  • \(dp[0][0] = 0\)
  • All others are \(\infty\)

• Transition: For each item \(A[i]\):

  • Do not select: \(dp[i+1][j] = \min(dp[i+1][j], dp[i][j])\)
  • Select: \(dp[i+1][j + A[i]] = \min(dp[i+1][j + A[i]], dp[i][j] + 1)\)
    (only when \(j + A[i] \leq S\))

• Finally:

  • \(dp[N][S]\) is the answer. If it is \(\infty\), output \(-1\)

Concrete Example

For example, when \(N=3\), \(S=5\), \(A=[2, 3, 1]\): - Item 2 (3 yen) and Item 3 (2 yen) give a total of 5 yen → 2 items - Item 1 (2 yen) and Item 3 (1 yen) are not enough - Item 2 alone is 3 yen; Items 1 and 2 together give 5 yen but also 2 items → The minimum number of items is 2

Complexity

• Time complexity: \(O(N \times S)\)
• Space complexity: \(O(N \times S)\)

Implementation Notes

• The DP table size should be \((N+1) \times (S+1)\)
• Do not forget the initial value \(dp[0][0] = 0\)
• In each transition, perform a range check (j + A[i] <= S) to avoid index errors
• At the end, check whether the result is infinity and output -1 if so

## Source Code

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    S = int(data[1])
    A = list(map(int, data[2:]))

    # dp[i][j] := i番目までの商品を使って合計j円にするときの最小個数
    # 初期化: 無限大で埋める（不可能な状態）
    INF = float('inf')
    dp = [[INF] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 0  # 0個の商品で合計0円は可能（0個選ぶ）

    # DP更新
    for i in range(N):
        for j in range(S + 1):
            # i番目の商品を選ばない場合
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            # i番目の商品を選ぶ場合（価格がA[i]）
            if j + A[i] <= S:
                dp[i + 1][j + A[i]] = min(dp[i + 1][j + A[i]], dp[i][j] + 1)

    # 結果出力
    result = dp[N][S]
    if result == INF:
        print(-1)
    else:
        print(result)

if __name__ == "__main__":
    main()

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