概要

この問題は、制限された重さの範囲内で宝物の価値の合計を最大化するナップサック問題です。

考察

この問題は典型的な「0-1 ナップサック問題」として知られています。
各宝物について「入れる」または「入れない」の2択があり、全部の組み合わせを試すと \(2^N\) 通りとなり、\(N\) が最大100なので現実的ではありません（計算量的に爆発します）。

また、貪欲法（例えば価値/重さの比率が高い順に選ぶ）もこの問題では正しく動作しません。これは、ナップサックの容量ギリギリまで使わないと最適にならないケースがあるためです。

この問題を効率よく解くには、動的計画法（DP）を使います。
特に、重さに関するDPテーブルを用意し、「ある重さ \(j\) 以下で得られる最大価値」を管理することで、各宝物を一度だけ使うという制約を満たしつつ最適解を求められます。

コードでは、DPテーブル dp[j] を「重さ \(j\) 以下で達成可能な最大価値」として定義し、各宝物を後ろから（逆順に）処理することで、1つの宝物が複数回使われることを防いでいます。

アルゴリズム

この問題は 0-1 ナップサック問題 であり、動的計画法（DP）を用いて解きます。

DPの定義

• dp[j] := 重さが \(j\) 以下であるときに得られる価値の最大値

更新方法

各宝物 \(i\)（重さ \(T_i\), 価値 \(S_i\)）に対して： - 重さ \(j\) を \(M\) から \(T_i\) まで 逆順に 更新していく - dp[j] = max(dp[j], dp[j - T_i] + S_i)

逆順に更新することで、1つの宝物を複数回選んでしまうのを防ぎます。

最終的な答え

max(dp) が求める最大価値になります。

計算量

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

実装のポイント

• DPテーブルをサイズ \(M+1\) で確保する
• 各宝物に対して、重さの大きい方から更新する（逆順）ことが重要
• 入力を高速に読み込むことで、大きな \(N\) でも時間内に処理可能

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    weights = [0] * N
    values = [0] * N
    
    index = 2
    for i in range(N):
        weights[i] = int(data[index])
        values[i] = int(data[index+1])
        index += 2

    # dp[j] := 重さj以下で達成可能な最大価値
    dp = [0] * (M + 1)
    
    for i in range(N):
        w = weights[i]
        v = values[i]
        # 逆順に更新することで、各アイテムを一度だけ使うことを保証
        for j in range(M, w - 1, -1):
            if dp[j] < dp[j - w] + v:
                dp[j] = dp[j - w] + v
    
    print(max(dp))

if __name__ == "__main__":
    main()

---

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