0/1ナップサック問題

🔥 Vibe プロンプト

「DPで0/1ナップサックを解決：N=5、W=10、アイテム=[(2,6),(5,9),(4,5),(3,7),(6,8)]。DPテーブルと選択アイテムを出力。」

0/1ナップサックとは？

0/1ナップサックは、重さと価値を持つN個のアイテムから、容量Wに収まるように選択して総価値を最大化するDPの古典的問題です。各アイテムは0回か1回だけ選べます。

| 性質 | 意味 | |------|------| | 状態 | dp[i][w] = 最初のi個のアイテム、重さ≤wでの最大価値 | | 漸化式 | dp[i][w] = max(スキップ, 採用) = max(dp[i-1][w], dp[i-1][w-wi] + vi) | | 初期 | dp[0][w] = 0, dp[i][0] = 0 | | 時間 | O(N × W) — 疑似多項式時間 | | 空間 | O(N × W) → 最適化後 O(W) |

実装

def knapsack_01(weights, values, capacity):
    """
    weights: 各アイテムの重さ
    values: 各アイテムの価値
    capacity: 最大重量
    戻り値: (最大価値, 選択されたインデックスリスト)
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    # DPテーブルを埋める
    for i in range(1, n + 1):
        wi, vi = weights[i-1], values[i-1]
        for w in range(1, capacity + 1):
            if wi <= w:
                # 選択肢1: スキップ | 選択肢2: 採用
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)
            else:
                dp[i][w] = dp[i-1][w]  # 入らない
    
    # バックトラックで選択アイテムを特定
    selected = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:  # アイテムi-1が採用された
            selected.append(i-1)
            w -= weights[i-1]
    
    return dp[n][capacity], selected

# 例: 5アイテム、容量10
weights = [2, 5, 4, 3, 6]
values = [6, 9, 5, 7, 8]
capacity = 10

max_val, items = knapsack_01(weights, values, capacity)

print(f"\n{'='*45}")
print(f"0/1ナップサック結果")
print(f"{'='*45}")
print(f"最大価値: {max_val}")
print(f"選択アイテム: {items}")
total_w = sum(weights[i] for i in items)
print(f"総重量: {total_w}/{capacity}")

# DPテーブル出力
print(f"\nDPテーブル:")
for i in range(n + 1):
    row = " ".join(f"{dp[i][w]:2}" for w in range(capacity + 1))
    print(f"i={i}: [{row}]")

空間最適化版

def knapsack_opt(weights, values, capacity):
    """O(W)空間、O(N×W)時間"""
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        wi, vi = weights[i], values[i]
        for w in range(capacity, wi - 1, -1):  # 逆順が重要！
            dp[w] = max(dp[w], dp[w-wi] + vi)
    return dp[capacity]

print(f"ナップサック（O(W)空間）: {knapsack_opt(weights, values, capacity)}")

まとめ

| 項目 | 詳細 | |------|------| | 状態定義 | dp[i][w] = i個のアイテム、重さ≤wでの最大価値 | | 漸化式 | dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi) | | 初期条件 | dp[0][] = 0, dp[][0] = 0 | | 時間計算量 | O(N×W) | | 空間計算量 | O(N×W) → 最適化後 O(W) | | バックトラック | dp[n][W]から逆順に選択アイテムを特定 |