概要

\(N\) 個の商品からいくつか選び、その合計金額をちょうど \(S\) 円にするとき、選ぶ商品の最小個数を求めよ。不可能な場合は \(-1\) を出力せよ。

考察

この問題は「ある条件（合計が \(S\) 円）を満たす集合の中で、要素数が最小のものを求めよ」という最適化問題です。

素朴な方法として、全組み合わせ（部分集合）を試すことを考えると、\(2^N\) 通りとなり、\(N=100\) の制約では現実的ではありません（TLE）。また、貪欲法などで安易に価格の高い順に選んでも、最適解にならないことがあります。

このような「ある値（合計金額）を作れるか？」という問題に対して有効なのが動的計画法（DP）です。

特に、「i番目までの商品を使って、ちょうどj円を作るのに必要な最小個数」を管理するDPテーブルを用いると、最終的に \(dp[N][S]\) に答えが格納されます。

初期状態として、\(dp[0][0] = 0\) （0個の商品で0円は可能）、それ以外は無限大（達成不可能）とします。

アルゴリズム

動的計画法（DP）を用いて以下のように処理を行います：

• 状態定義：

  • \(dp[i][j]\) := \(i\) 番目までの商品を使って合計をちょうど \(j\) 円にするときの最小個数（達成できない場合は \(\infty\)）

• 初期化：

  • \(dp[0][0] = 0\)
  • その他は \(\infty\)

• 遷移： 各商品 \(A[i]\) について、

  • 選ばない：\(dp[i+1][j] = \min(dp[i+1][j], dp[i][j])\)
  • 選ぶ：\(dp[i+1][j + A[i]] = \min(dp[i+1][j + A[i]], dp[i][j] + 1)\)
    （ただし、\(j + A[i] \leq S\) の範囲）

• 最終的に：

  • \(dp[N][S]\) が答え。\(\infty\) なら \(-1\) を出力

具体例

例えば、\(N=3\), \(S=5\), \(A=[2, 3, 1]\) のとき： - 商品2（3円）と商品3（2円）で合計5円 → 個数2 - 商品1（2円）と商品3（1円）では足りない - 商品2単体では3円、商品1と2では5円だが個数2で同じ → 最小個数は2

計算量

• 時間計算量: \(O(N \times S)\)
• 空間計算量: \(O(N \times S)\)

実装のポイント

• DPテーブルのサイズは \((N+1) \times (S+1)\) とすること
• 初期値 \(dp[0][0] = 0\) を忘れずに
• 各遷移においてインデックスエラーにならないように、範囲チェック（j + A[i] <= S）を行うこと
• 最後に結果が無限大かどうかを判定して -1 を出力する

## ソースコード

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

---

この解説は qwen3-coder-480b によって生成されました。