【解説】　ナップザック問題

種類が３つの次の石がある。石0（価値1，重量2），石1（価値2，重量2），石2（価値4，重量3）。ナップザックの容量を5とするとき，ナップザックに入れた石の価値の合計は最大いくつか？　ただし、各石はそれぞれ 1 個までしか選ぶことができないものとする。

# ナップザック問題のPythonコード

def solve_knapsack():
    # 石のデータ (価値, 重量)
    items = [
        (1, 2),  # 石 0
        (2, 2),  # 石 1
        (4, 3)   # 石 2
    ]
    capacity = 5
    n = len(items)

    # DPテーブルの初期化 (n+1 行 x capacity+1 列)
    # dp[i][j] は「i番目までの石を使って、容量j以下で作れる最大価値」
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # DPテーブルの更新
    for i in range:
        value, weight = items[i]
        for j in range(capacity + 1):
            if j < weight:
                # 石 i を入れられない場合
                dp[i + 1][j] = dp[i][j]
            else:
                # 「石 i を入れない場合」と「石 i を入れる場合」の大きい方を採用
                dp[i + 1][j] = max(dp[i][j], dp[i][j - weight] + value)

    return dp[n][capacity]

# 実行
max_value = solve_knapsack()
print(f"ナップサックに入れた石の価値の合計の最大値は: {max_value}")

解説

このコードでは、以下の考え方で最大値を導き出しています。

1. DPテーブルの作成: 縦軸に検討する石の数、横軸に容量（0〜5）をとった表を作ります。

2. 判断の分岐: 各ステップで「今の石を入れるか、入れないか」を比較します。

   • 入れない場合: 1つ前のステップの価値をそのまま引き継ぐ。

   • 入れる場合: 「（容量 － 今の石の重量）の時の最大価値」に「今の石の価値」を足す。

3. 最終結果: 石を3つすべて検討し終えた、容量5の地点（dp[3][5]）が答えになります。

「その時点（行）までの石を使って」という言葉を、**「選択肢として選べる石を一つずつ増やしていく」**と言い換えると分かりやすくなります。

これを視覚的に理解するために、**「もしお店に、石が1種類しかなかったら？」「2種類に増えたら？」**と、順を追ってシミュレーションしてみましょう。

ステップ1：石0（重2, 価1）しか世界にない場合

まず、あなたの手元には「石0」しか選択肢がありません。

• 容量1のバッグ：石0（重2）は入らないので、価値は 0

• 容量2のバッグ：石0が入るので、価値は 1

• 容量5のバッグ：石0を1個入れるだけなので、価値は 1 のまま

これが1行目の意味です。「石0だけを使えるなら、こうなる」という限界を示しています。

ステップ2：石1（重2, 価2）も選べるようになった場合

次に、新しく「石1」がお店に並んだと考えます。ここで、「石0だけを使っていた時の結果」と比較します。

• 容量2のバッグのとき：

  • 前のまま（石0）なら価値1。

  • 新しく出た「石1」に入れ替えると価値 2。

  • → だから、このマスの最大価値は 2 に更新されます。

• 容量4のバッグのとき：

  • 前のまま（石0）なら価値1。

  • でも「石1（重2）」を入れたあと、まだ容量が2余っています。

  • その余った容量2には、**「石0（ステップ1での最大値）」**を入れられます。

  • → 石1の価値(2) ＋ 石0の価値(1) ＝ 3。これがこの時点の最大です。

ステップ3：石2（重3, 価4）も選べるようになった場合（最終段階）

最後に「石2」が登場します。

• 容量5のバッグのとき（最終的な答え）：

  • 石2（重3）を入れないなら、前のステップでの最大値 3 のまま。

  • 石2（重3, 価4）を 入れる と決めた場合、残りの容量は 2 です（5 - 3 = 2）。

  • 「容量2のときに、これまでの石（石0, 1）で詰め込める最大価値」をステップ2の表から探すと、2 だとわかります。

  • → 石2の価値(4) ＋ 残り容量で作れる価値(2) ＝ 6。