5.2 子集合加總與背包問題#

概念說明#

子集合加總（SUBSET-SUM）：給定一個正整數集合 S 與目標值 t，問是否存在 S 的子集，其元素總和恰好等於 t。例如 S = {3, 9, 14, 20, 27}、t = 23，答案是 {3, 20}。這個問題看似只是小學加法遊戲，卻是 NP-complete 家族中的核心成員。

SUBSET-SUM 之所以重要，是因為它是「數值型」NP-complete 問題的代表：它的輸入是數字而非結構（圖、公式），因此成為連接邏輯問題（3-SAT）與組合優化問題（背包、分割）之間的化約樞紐——第六章我們就會實際動手做這兩個化約。

背包問題（0/1 Knapsack）：給定 n 個物品，第 i 個物品有重量 wᵢ 與價值 vᵢ，背包容量 W，問在不超重的前提下能裝入的最大總價值。背包問題是 NP-hard 的優化版本；它的判定版本（「能否達到價值至少 V？」）屬於 NP-complete。背包問題在現實中無所不在：預算分配、投資組合、廣告位選擇、記憶體配置，本質上都是背包。

兩者的關係很密切：SUBSET-SUM 是背包的特例——令每個物品重量等於價值（wᵢ = vᵢ = sᵢ）、容量 W = t，此時「價值能否達到 t」就等價於「子集和能否等於 t」。因此背包不比 SUBSET-SUM 簡單。

演算法步驟#

SUBSET-SUM 的動態規劃解法（偽多項式時間）：

建立布林表 dp[j]，dp[j] = True 表示可以湊出總和 j，初始只有 dp[0] = True。
依序處理每個數字 s ∈ S。
對每個 j 從大到小（避免同一數字被重複使用）更新：dp[j] = dp[j] or dp[j - s]。
全部處理完後，dp[t] 即為答案。
若需要還原子集，額外記錄每個 j 是由哪個數字達成的，再回溯。

背包問題的動態規劃：

建立二維表 dp[i][j]：前 i 個物品、容量 j 時的最大價值。
dp[i][j] = max(dp[i-1][j], dp[i-1][j-wᵢ] + vᵢ)（不拿第 i 個物品 vs. 拿）。
答案為 dp[n][W]，可用滾動陣列把空間降到 O(W)。

Python 程式碼範例#

def subset_sum(S, t):
    """動態規劃：O(n*t) 偽多項式時間"""
    dp = [False] * (t + 1)
    dp[0] = True
    choice = [None] * (t + 1)          # 記錄 j 由哪個數字達成
    for s in S:
        for j in range(t, s - 1, -1):  # 由大到小，避免重複使用
            if not dp[j] and dp[j - s]:
                dp[j] = True
                choice[j] = s
    if not dp[t]:
        return None
    # 回溯還原子集
    subset, j = [], t
    while j > 0:
        s = choice[j]
        subset.append(s)
        j -= s
    return subset

def knapsack(weights, values, W):
    """0/1 背包：O(n*W) 時間，O(W) 空間"""
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(W, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[W]

S, t = [3, 9, 14, 20, 27], 23
print(subset_sum(S, t))                       # [20, 3]
print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8))  # 10

複雜度分析#

SUBSET-SUM 暴力法：O(2ⁿ)——列舉所有子集。
SUBSET-SUM 動態規劃：O(n·t) 時間、O(t) 空間。注意 t 是數值而非輸入長度：t 以二進位表示只需 log t 個位元，因此這是偽多項式演算法，不違反 P ≠ NP 的猜測。
背包動態規劃：O(n·W) 時間，同樣是偽多項式。
當 t、W 與 n 同階（即數字本身很大）時，動態規劃退化為指數時間，這正是 NP-hard 的體現。

練習#

用 subset_sum 檢查 S = {1, 2, 4, 8, 16, 32} 能否湊出 0 到 63 之間的所有整數，並解釋為什麼這組數字有此性質（提示：二進位）。
修改 knapsack，加入回溯邏輯，回傳被選中的物品編號列表而不只是最大價值。
生成 20 個隨機實例（n = 20，數字範圍 1~100），比較動態規劃與暴力法（2²⁰ 種子集）的執行時間，並繪製或列表比較。