Overview

Given \(N\) items, the problem asks to find the minimum number of items to select such that their total price is exactly \(S\) yen. This is an application of the “subset sum problem” and can be solved efficiently using dynamic programming (DP).

Analysis

To solve this problem, let’s first consider a naive brute-force approach that “tries whether to select or not select each item.” However, since the number of items \(N\) can be up to \(100\), the number of combinations would be \(2^{100}\), which cannot be computed within the time limit.

Therefore, we focus on the property that if we know “the minimum number of items to make a certain amount,” we can use it to determine the minimum number of items for even larger amounts.

• Desired value: the minimum number of items to make a total of \(S\) yen
• State definition: dp[j] = the minimum number of items needed to make a total amount of \(j\) yen

With this state definition, each time we add a new item (with price \(A_i\)), we can consider the transition “add that item to the current amount \(j - A_i\) to make amount \(j\).”

Algorithm

Dynamic Programming (DP)

The computation proceeds as follows:

1. Initialization:
   • Create an array dp of size \(S+1\).
   • Set dp[0] = 0 (0 items are needed to make 0 yen), and fill all other entries with a very large value (inf). Here, we use a value exceeding the maximum number of items \(N\) (e.g., \(N+1\)) as inf.
2. Table Update:
   • For each item \(A_i\), repeat the following process.
   • Check amounts \(j\) from \(S\) down to \(A_i\) in reverse order, updating dp[j].
   • Update formula: dp[j] = min(dp[j], dp[j - A_i] + 1)
   • *The reason for updating in reverse order is to prevent the same item from being used multiple times in a single update (the same idea as the 0/1 knapsack problem).
3. Output the Answer:
   • If dp[S] remains at its initial value (inf), it is impossible to make a total of \(S\) yen, so output -1.
   • Otherwise, output the value of dp[S].

Complexity

• Time Complexity: \(O(N \times S)\)
  • This is because we loop over amounts up to \(S\) inside a loop over \(N\) items.
  • Under the given constraints (\(N \leq 100, S \leq 10000\)), the computation is at most around \(10^6\) operations, which is well within the time limit.
• Space Complexity: \(O(S)\)
  • This is because we use a one-dimensional array that stores states up to amount \(S\).

Implementation Notes

• Initial Value Setting: Since this is a minimization problem, the initial values should be set to a sufficiently large value.

• Preventing Duplicates: Since each item can only be used once, the inner loop must iterate in reverse order from \(S\) down to \(A_i\). If iterated in forward order (from \(A_i\) to \(S\)), it would compute the case where the same item is used multiple times.

• Feasibility Check: By checking whether dp[S] is still greater than the initial value at the end, we can determine whether the target amount can be achieved.

  Source Code

import sys

def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 商品数 N と目標合計金額 S
    n = int(input_data[0])
    s = int(input_data[1])
    # 各商品の価格 A
    a = list(map(int, input_data[2:]))
    
    # dp[j] は合計金額が j 円になる時の最小の商品数
    # 初期値として、ありえない大きな値（N+1）を入れておく
    inf = n + 1
    dp = [inf] * (s + 1)
    
    # 0円を作るのに必要な商品数は 0 個
    dp[0] = 0
    
    # 各商品について、DPテーブルを更新する
    for price in a:
        # 重複して選ばないよう、後ろから更新する（0/1ナップサック問題の考え方）
        for j in range(s, price - 1, -1):
            if dp[j - price] + 1 < dp[j]:
                dp[j] = dp[j - price] + 1
                
    # 目標金額 S に到達可能か判定
    if dp[s] > n:
        print("-1")
    else:
        print(dp[s])

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.