0/1 背包問題

什麼是 0/1 背包？

0/1 背包問題是 DP 最經典的問題：給定 N 個物品（每個有重量和價值），選擇一個子集放入容量 W 的背包中，使總價值最大化。每個物品只能取 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):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    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:
                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]:
            selected.append(i-1)
            w -= weights[i-1]
    
    return dp[n][capacity], selected

# 範例
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最大價值: {max_val}")
print(f"選取物品: {items}")
total_w = sum(weights[i] for i in items)
print(f"總重量: {total_w}/{capacity}")

# 輸出 DP 表格
print(f"\nDP 表格：")
print(f"      " + " ".join(f"{w:>3}" for w in range(capacity + 1)))
for i in range(n + 1):
    row = " ".join(f"{dp[i][w]:>3}" 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] 逆向尋找選取物品 |

常見問題與解決方案

| 問題 | 原因 | 解法 | |------|------|------| | 結果不如預期 | 參數設定不當 | 檢查預設值與邊界條件 | | 執行速度慢 | 演算法效率低 | 考慮使用更高效的資料結構 | | 記憶體不足 | 資料量過大 | 使用批次處理或串流方式 | | 難以除錯 | 缺乏日誌 | 加入詳細的 log 輸出 |

---

---

0/1 背包：動態規劃的經典應用

0/1 背包問題（每個物品只能選或不選）是動態規劃最經典的應用之一。理解它就能理解 DP 的核心——狀態定義和狀態轉移。

DP 解背包的關鍵

狀態：dp[i][w] = 前 i 個物品中，在容量 w 的限制下能達到的最大價值

轉移：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])
                ↑ 不選第 i 個    ↑ 選第 i 個（前提：裝得下）

時間複雜度

| 方法 | 時間 | 空間 | 適合 | |:----|:----|:----|:----| | 二維 DP | O(nW) | O(nW) | 教學用、容易理解 | | 一維 DP（滾動陣列） | O(nW) | O(W) | 實戰用、省記憶體 |

一維陣列最佳化

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 從右到左遍歷，避免重複使用同一物品
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

下一章預告：最長共同子序列 LCS

背包問題是最佳化型的 DP。下一章的 LCS 是字串比對型的 DP——找出兩個字串之間最長的共同部分，應用在拼寫檢查、DNA 比對、版本差異分析。