概要

\(N\) 個の商品から好きなものを選び、合計金額が予算 \(K\) 円以下で最大となる組み合わせを求める問題です。これは典型的な 0-1 ナップサック問題（部分和問題） です。

考察

素朴なアプローチ

\(N\) 個の商品それぞれについて「買う／買わない」の2通りがあるので、全ての組み合わせは \(2^N\) 通りです。\(N\) が最大 \(100\) の場合、\(2^{100}\) は天文学的な数であり、全探索では到底間に合いません（TLE）。

重要な気づき

この問題では「合計金額が \(K\) 以下か？」だけが重要であり、\(K \leq 10^4\) と比較的小さいです。そこで、「合計金額としてちょうど \(j\) 円を実現できるか？」 を \(j = 0, 1, 2, \ldots, K\) のそれぞれについて管理する動的計画法（DP）が使えます。

具体例

例えば \(N = 3\), \(K = 10\), \(C = [3, 5, 7]\) の場合： - 何も買わない → 合計 \(0\) 円 ✓ - \(\{3\}\) → \(3\) 円 ✓ - \(\{5\}\) → \(5\) 円 ✓ - \(\{3, 5\}\) → \(8\) 円 ✓ - \(\{7\}\) → \(7\) 円 ✓ - \(\{3, 7\}\) → \(10\) 円 ✓ ← これが最大 - \(\{5, 7\}\) → \(12\) 円 ✗（\(K\) を超える）

DP を使えば、これらを効率的に判定できます。

アルゴリズム

0-1 ナップサック型の部分和 DP を使います。

1. DP 配列の定義: dp[j] = 「いくつかの商品を選んで合計金額をちょうど \(j\) 円にできるか（True/False）」
2. 初期状態: dp[0] = True（何も買わなければ合計 \(0\) 円）、それ以外は False
3. 遷移: 各商品 \(c\) について、\(j = K, K-1, \ldots, c\) の順に逆向きにループし、dp[j - c] が True なら dp[j] = True とする
   • 逆順にループする理由: 同じ商品を2回以上使ってしまうのを防ぐためです。順方向にループすると、1つの商品の効果が何度も伝播してしまいます。
4. 答えの取得: \(j = K, K-1, \ldots, 0\) の順に見て、最初に dp[j] が True となる \(j\) が答え

計算量

• 時間計算量: \(O(N \times K)\)
  • 商品 \(N\) 個それぞれについて、\(K\) 以下の各金額を走査するため
  • 最大で \(100 \times 10^4 = 10^6\) 程度なので十分高速
• 空間計算量: \(O(K)\)
  • 1次元の DP 配列のみを使用

実装のポイント

• 逆順ループが最重要: for j in range(K, c - 1, -1) のように \(K\) から \(c\) まで降順にループすることで、各商品を最大1回しか選ばないことを保証しています。もし昇順（range(c, K+1)）にすると、同じ商品を複数回使ってしまう（重複あり部分和問題になる）ので注意が必要です。

• dp[j - c] が True のとき dp[j] = True とするだけのシンプルな更新式です。

• 最後に dp[j] が True となる最大の \(j\) を探すことで、\(K\) 以下の最大合計金額が求まります。

  ソースコード

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

dp = [False] * (K + 1)
dp[0] = True

for c in C:
    for j in range(K, c - 1, -1):
        if dp[j - c]:
            dp[j] = True

for j in range(K, -1, -1):
    if dp[j]:
        print(j)
        break

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