概要

\(N\) 個の商品から何個か選び、価格の合計がちょうど \(S\) 円となるようにしたい。そのような選び方が存在する場合は最小個数を、存在しない場合は \(-1\) を求める問題です。これは 0/1 ナップサック問題 の変種として、動的計画法（DP）で解くことができます。

考察

素朴なアプローチ（全探索）

\(N\) 個の商品それぞれについて「選ぶ / 選ばない」の2通りがあるため、全探索すると \(2^N\) 通りの組合せを調べることになります。\(N = 100\) のとき \(2^{100} \approx 10^{30}\) となり、到底間に合いません。

重要な気づき

この問題は「合計金額がちょうど \(S\) になるか」と「なるならば最小個数はいくつか」を同時に求める必要があります。ここで注目すべきは：

• 各商品は1回しか選べない（0/1 ナップサック）
• 目標金額 \(S\) が最大 \(10000\) と比較的小さい

これにより、金額を状態としたDPが効率的に使えます。

DP の定義

\(dp[j]\) = 「商品の価格の合計がちょうど \(j\) 円となるように選んだときの、最小個数」

と定義します。初期値は \(dp[0] = 0\)（何も選ばなければ合計 \(0\) 円、個数 \(0\) 個）、それ以外は \(\infty\)（まだ実現不可能）とします。

遷移

商品 \(i\)（価格 \(A_i\)）を考えるとき、各金額 \(j\) について：

\[dp[j] = \min(dp[j],\ dp[j - A_i] + 1)\]

と更新します。「\(j - A_i\) 円を作る方法に、商品 \(i\) を1つ追加して \(j\) 円にする」という意味です。

逆順ループの理由

同じ商品を2回以上使わないために、\(j\) を \(S\) から \(A_i\) まで逆順 にループします。もし昇順にすると、更新済みの \(dp[j - A_i]\) を使ってしまい、同じ商品を複数回選んだことになってしまいます。

アルゴリズム

1. \(dp[0] = 0\)、\(dp[1], dp[2], \ldots, dp[S] = \infty\) で初期化する。
2. 各商品 \(i = 0, 1, \ldots, N-1\) について：
   • \(j = S, S-1, \ldots, A_i\) の順にループし、\(dp[j] = \min(dp[j],\ dp[j - A_i] + 1)\) で更新する。
3. 最終的に \(dp[S]\) が \(\infty\) のままなら \(-1\) を、そうでなければ \(dp[S]\) を出力する。

具体例

\(N = 3,\ S = 7,\ A = [3, 4, 5]\) の場合：

• 初期: \(dp = [0, \infty, \infty, \infty, \infty, \infty, \infty, \infty]\)
• 商品1（価格3）処理後: \(dp[3] = 1\)
• 商品2（価格4）処理後: \(dp[4] = 1,\ dp[7] = 2\)
• 商品3（価格5）処理後: \(dp[5] = 1,\ dp[8]\) は範囲外なので変化なし

結果: \(dp[7] = 2\)（商品1と商品2を選ぶ）

計算量

• 時間計算量: \(O(N \times S)\) — 商品ごとに金額 \(S\) までのループを回すため
• 空間計算量: \(O(S)\) — 1次元の DP 配列のみ使用

\(N \leq 100,\ S \leq 10000\) なので、最大でも \(100 \times 10000 = 10^6\) 回程度の操作で十分高速に動作します。

実装のポイント

• 逆順ループを忘れると、同じ商品を複数回使ってしまう（完全ナップサック問題になってしまう）ので要注意。

• DP の初期値に float('inf') を使うことで、「まだその金額が実現できていない」状態を自然に表現できる。

• 最後に \(dp[S]\) が \(\infty\) かどうかで、実現可能性の判定と最小個数の出力を同時に行える。

  ソースコード

def solve():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    
    # dp[j] = minimum number of items to make sum exactly j
    INF = float('inf')
    dp = [INF] * (S + 1)
    dp[0] = 0
    
    for i in range(N):
        # Traverse in reverse to ensure each item is used at most once (0/1 knapsack)
        for j in range(S, A[i] - 1, -1):
            if dp[j - A[i]] + 1 < dp[j]:
                dp[j] = dp[j - A[i]] + 1
    
    print(dp[S] if dp[S] != INF else -1)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。