概要

予算 \(K\) 円以内で購入できる商品の組み合わせのうち、合計金額を最大にする問題です。

考察

この問題は「ナップサック問題」の一種と考えることができます。
各商品は「価格」だけを持ち、選ぶか選ばないかの2択があります。目標は、価格の合計が \(K\) 以下になるように選び、その合計を最大化することです。

素朴な方法として、すべての商品の部分集合を試す方法（全探索）がありますが、商品数 \(N\) が最大100なので、\(2^{100}\) 通りとなり、現実的ではありません（TLE）。

そこで、動的計画法（DP）を使うことを考えます。
この問題では、「ある金額 \(w\) をちょうど使うことができるか？」という真偽値を管理するDPテーブルを作ると効率的に解けます。
つまり、dp[w] = True なら、合計がちょうど \(w\) 円になる商品の選び方が存在することを意味します。

初期状態では dp[0] = True（何も買わなければ0円）とし、商品を1つずつ見て、その商品を使って到達可能な金額を更新していきます。

更新の際に注意すべきは、同じ商品を複数回使わないようにするために、金額の大きい方から小さい方へループを回すことです（典型的なDPのテクニック）。

最後に、dp[w] == True となる最大の \(w\)（ただし \(w \leq K\)）が答えになります。

例

例えば、入力が以下のとき：

N=3, K=5
C = [2, 3, 4]

• 最初: dp = [True, False, False, False, False, False]
• 商品2円を処理 → dp = [True, False, True, False, False, False]
• 商品3円を処理 → dp = [True, False, True, True, False, True]
• 商品4円を処理 → dp = [True, False, True, True, True, True]

この中で最大のTrueのインデックスは5なので、答えは5円。

アルゴリズム

この問題は 部分和問題の応用 として解くことができます。

• DP配列 dp[w] を「合計金額をちょうど \(w\) 円にできるか？」の真偽値で管理する。
• 初期状態：dp[0] = True
• 各商品の価格 \(c\) に対して、\(K\) 円から \(c\) 円まで逆順にループし、遷移を行う：
  • if dp[w - c]: dp[w] = True
• 最後に、dp[w] == True となる最大の \(w \leq K\) を探す。

計算量

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

実装のポイント

• DPテーブルの更新は必ず 大きい金額から小さい金額に向かって行うこと（同じ商品を複数回使わないようにするため）。
• DPテーブルは bool 型の1次元配列で十分。
• 最後に dp[w] == True となる最大の \(w\) を探す処理が必要。

## ソースコード

```python
N, K = map(int, input().split())
C = list(map(int, input().split()))

# dp[i][w] := i番目までの商品を使って、ちょうどw円になるか？
dp = [False] * (K + 1)
dp[0] = True

for c in C:
    # 後ろから更新することで、同じ商品を複数回使わないようにする
    for w in range(K, c - 1, -1):
        if dp[w - c]:
            dp[w] = True

# dp[w] == True となる最大の w を求める
max_total = 0
for w in range(K + 1):
    if dp[w]:
        max_total = w

print(max_total)

---

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