概要

商品の価格リストから合計金額がちょうどS円になるように商品を選ぶとき、必要な最小個数を求める問題です。

考察

この問題は「部分和問題」の変種で、合計金額がSになる組み合わせの中から最小の商品個数を求める必要があります。各商品を選ぶ/選ばないの組み合わせを全て試すと\(2^N\)通りになり、Nが最大100の場合には計算量が爆発してしまいます。そのため、動的計画法を用いて効率的に解く必要があります。

アルゴリズム

動的計画法を用いて解きます。配列dp[i]を「合計金額をi円にするために必要な最小の商品個数」と定義します。初期状態ではdp[0] = 0（0円にするには0個の商品）とし、他の値は無限大（不可能）で初期化します。

各商品について、価格をpriceとしたとき、合計金額がj円になる最小個数は、j-price円の最小個数に1を加えたもの（この商品を選ぶ場合）と、現在のdp[j]の値（この商品を選ばない場合）の小さい方になります。これをSからpriceまで降順で更新していくことで、同じ商品を複数回選ぶことを防ぎます。

計算量

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

実装のポイント

• 配列を無限大（INF）で初期化し、達成不可能な状態を表現する

• 合計金額のループを降順（Sからpriceまで）で回すことで、同じ商品を重複して選ぶことを防ぐ

• 最終的にdp[S]がINFでなければその値を、INFならば-1を出力する

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    S = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    INF = float('inf')
    dp = [INF] * (S + 1)
    dp[0] = 0
    
    for price in A:
        for j in range(S, price - 1, -1):
            if dp[j - price] != INF:
                dp[j] = min(dp[j], dp[j - price] + 1)
    
    print(dp[S] if dp[S] != INF else -1)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。