概要

\(N\) 個の商品の中から、価格の合計がちょうど \(S\) 円になるように選ぶとき、選ぶ商品の最小個数を求める問題です。これは「部分和問題」の応用であり、動的計画法（DP）を用いることで効率的に解くことができます。

考察

この問題を解くにあたって、まず「全ての商品について選ぶか選ばないかを試す」という素朴な全探索を考えてみます。しかし、商品の個数 \(N\) が最大 \(100\) であるため、組み合わせの数は \(2^{100}\) 通りとなり、制限時間内に計算が終わりません。

そこで、「ある金額を作るための最小個数」が分かれば、それを利用してさらに大きな金額の最小個数を求められるという性質に注目します。

• 求めたい値：合計 \(S\) 円にするための最小個数
• 状態の定義：dp[j] = 合計金額を \(j\) 円にするために必要な最小の商品数

このように状態を定義すると、新しい商品（価格 \(A_i\)）を追加するたびに、「現在の金額 \(j - A_i\) にその商品を追加して金額 \(j\) を作る」という遷移を考えることができます。

アルゴリズム

動的計画法（DP）

以下の手順で計算を行います。

1. 初期化:
   • 配列 dp をサイズ \(S+1\) で作成します。
   • dp[0] = 0（0円を作るのに必要な個数は0個）とし、それ以外を非常に大きな値（inf）で埋めます。ここでは最大個数 \(N\) を超える値（例：\(N+1\)）を inf とします。
2. テーブルの更新:
   • 各商品 \(A_i\) について、以下の処理を繰り返します。
   • 金額 \(j\) を \(S\) から \(A_i\) まで後ろから順に確認し、dp[j] を更新します。
   • 更新式：dp[j] = min(dp[j], dp[j - A_i] + 1)
   • ※後ろから更新する理由は、同じ商品を一度の更新で何度も使わないようにするためです（0/1ナップサック問題と同じ考え方）。
3. 答えの出力:
   • dp[S] が初期値（inf）のままであれば、合計 \(S\) 円にすることは不可能なので -1 を出力します。
   • そうでなければ、dp[S] の値を出力します。

計算量

• 時間計算量: \(O(N \times S)\)
  • 商品数 \(N\) 回のループの中で、金額 \(S\) 回のループを回すためです。
  • 今回の制約（\(N \leq 100, S \leq 10000\)）では、最大でも \(10^6\) 回程度の計算となり、十分に間に合います。
• 空間計算量: \(O(S)\)
  • 金額 \(S\) までの状態を保持する1次元配列を使用するためです。

実装のポイント

• 初期値の設定: 最小値を求める問題なので、初期値には十分大きな値を設定します。

• 重複の防止: 1つの商品は1度しか使えないため、内側のループを S から A_i に向かって逆順に回す必要があります。もし正順（A_i から S）で回すと、同じ商品を何個も使った場合の計算になってしまいます。

• 判定: 最後に dp[S] が初期値より大きいかどうかを確認することで、目標金額が作れたかどうかを判定できます。

  ソースコード

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()

この解説は gemini-3-flash-thinking によって生成されました。