概要

\(N\) 個の商品の中からいくつかを選び、合計金額をちょうど \(S\) 円にする方法があるかを判定し、可能なら「選ぶ個数の最小値」を求める問題です。

考察

• 各商品は 選ぶ／選ばないの2択で、同じ商品を複数回選ぶことはできません（0/1 の選択）。
• 目的は「合計 \(S\) を作れるか」だけでなく、作れる場合の 最小個数なので、単なる到達判定（真偽）では不十分です。

素朴な方法が難しい理由

• 全ての部分集合を試すと \(2^N\) 通りで、\(N \le 100\) では現実的に間に合いません。
• 「合計 \(S\) を作れるか」を DP で判定する方法は有名ですが、今回はさらに「最小個数」も必要です。

解決の方針

• 「合計金額 \(s\) を作るのに必要な最小個数」を DP で管理します。
• 各商品を順に見て、「この商品を使う場合」を反映していけば、最小個数も同時に求められます。

例えば \(S=7\), 商品が \([2,3,5]\) のとき、 - \(7=2+5\) なら 2 個 - \(7=2+3+? \) は作れない
よって答えは 2、というように「最小個数」を DP で更新していきます。

アルゴリズム

0/1 ナップサック型 DP（最小個数版）を使います。

• 配列 \(dp[s]\) を「合計 \(s\) 円を作るのに必要な最小個数」と定義する
• 初期化：
  • \(dp[0]=0\)（0円は何も選ばず作れる）
  • それ以外は到達不可能として \(dp[s]=\infty\)
• 各商品価格 \(a\) について、以下で更新：
  • \(s\) を 大きい方から \(S,S-1,\dots,a\) と降順に動かし、
  • もし \(dp[s-a]\) が到達可能なら、\(dp[s] = \min(dp[s],\ dp[s-a]+1)\) とする

降順ループにするのが重要で、これにより「同じ商品を1回だけ使う（0/1）」が保証されます。昇順にすると同じ商品を何度も使った更新（無限個使える問題）になってしまいます。

最後に、 - \(dp[S]\) が \(\infty\) のままなら不可能なので \(-1\) - そうでなければ \(dp[S]\) を出力します

計算量

• 時間計算量: \(O(NS)\)（各商品ごとに \(0 \sim S\) の更新）
• 空間計算量: \(O(S)\)（一次元 DP のみ）

実装のポイント

• 降順ループ（for s in range(S, a-1, -1)）にすることで、同じ商品を複数回使う誤りを防ぎます。

• 到達不可能を表す値として十分大きい INF を使い、最後に dp[S] >= INF かで判定します。

• \(a > S\) の商品は合計 \(S\) に寄与できないのでスキップして構いません（高速化にもなる）。

  ソースコード

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

---

この解説は gpt-5.2-high によって生成されました。