概要

予算 \(K\) 円以内で商品を選び、合計金額を最大化する典型的なナップサック問題です。

考察

この問題は「0-1ナップサック問題」の一種で、各商品を最大1回まで選ぶことができます。素朴な全探索では \(2^N\) 通りの選び方を調べる必要があり、\(N\) が最大100の場合 \(2^{100}\) は非常に大きいため現実的ではありません。代わりに動的計画法を用いることで、効率的に解を求めることができます。

アルゴリズム

動的計画法を用いて解きます。配列 dp をサイズ \(K+1\) で初期化し、dp[j] には予算 \(j\) 円まで使えるときの合計金額の最大値を記録します。

各商品について、予算 \(K\) 円から商品の価格 \(c\) 円まで降順にループします。各予算 \(j\) について、商品を選ばない場合（現在の dp[j]）と選ぶ場合（dp[j - c] + c）を比較し、大きい方を採用します。降順で処理することで、同じ商品を重複して選ぶのを防ぎます。

最終的に dp 配列の最大値が、予算 \(K\) 円以内で達成できる最大の合計金額となります。

計算量

• 時間計算量: \(O(N \cdot K)\)
• 空間計算量: \(O(K)\)

実装のポイント

• 配列 dp は0で初期化します

• 内側のループは降順（\(K\) から \(c\) まで）で処理することが重要です（昇順だと同じ商品を複数回選んでしまう）

• max(dp) で最終的な答えを得ます（dp[K] が最大値とは限らないため）

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    K = int(data[1])
    C = list(map(int, data[2:2+n]))
    
    dp = [0] * (K + 1)
    
    for c in C:
        for j in range(K, c - 1, -1):
            if dp[j] < dp[j - c] + c:
                dp[j] = dp[j - c] + c
                
    print(max(dp))

if __name__ == "__main__":
    main()

---

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