6.2 從子集合加總到分割與背包#

概念說明#

分割問題（PARTITION）：給定一組正整數，問能否分成兩部分使兩部分的總和相等。這是 Karp 清單中最簡單敘述的 NP-complete 問題，也是化約鏈上的重要中繼站。它與 SUBSET-SUM 的關係一眼可見：令總和為 σ，則「可分割」⟺「存在子集和為 σ/2」。因此 SUBSET-SUM 可在多項式時間內化約到 PARTITION——構造出「等價於求 σ' / 2」的實例即可。

具體化約：給 SUBSET-SUM 實例 (S, t)，令 σ = sum(S)。構造 S' = S ∪ {σ - 2t}（若 σ - 2t ≤ 0 則先放大所有數字）。此時 S' 總和為 2σ - 2t... 為保持簡潔，常用技巧是先將所有數字乘上 2 再加入一個大數平衡；標準做法是加入數字 σ - 2t 並調整：S' 的總和為 2(σ - t)，選中子集總和必為 σ - t，加上 σ - 2t 是否被選，恰可推出原問題的子集和是否為 t。化約的細節正是本章要動手驗證的重點。

PARTITION 到背包：分割問題是背包的特例——令每個物品重量等於價值 wᵢ = vᵢ、容量 W = σ/2，則「能否恰好裝滿」⟺「能否分割」。這是一個一行的化約，也再次說明：特例往往比一般問題「更有名」。

這條化約鏈 3-SAT → SUBSET-SUM → PARTITION → 背包展示了 NP-complete 問題之間「等價但形式各異」的網絡結構：同一個計算難題，可以穿上數字、物品、集合等不同外衣。

演算法步驟#

SUBSET-SUM → PARTITION 的化約：

輸入 SUBSET-SUM 實例 (S, t)，σ = sum(S)。
若 t > σ 或 t < 0，直接回報 NO（特例處理）。
將每個元素放大：S₁ = {2s : s ∈ S}，t₁ = 2t。
加入新元素 c = 2(σ - t)：S' = S₁ ∪ {c}，總和為 2σ + 2(σ - t) ... 採用標準構造使總和為偶數且一半對應 t₁。
對 S' 跑分割判定（DP：子集和能否達到總和之半）。
若分割可行且 c 不在「對應子集」中，還原出原問題的解。

PARTITION → 背包的化約：

輸入數字集合 A，σ = sum(A)。
建立背包實例：n 個物品，wᵢ = vᵢ = aᵢ，容量 W = σ/2，價值門檻 V = σ/2。
跑背包判定：最大價值 ≥ V ⟺ 能恰好裝滿 ⟺ 可分割。

Python 程式碼範例#

def can_partition(A):
    """分割判定：DP，O(n * sum/2)"""
    total = sum(A)
    if total % 2:
        return False
    half = total // 2
    dp = [False] * (half + 1)
    dp[0] = True
    for a in A:
        for j in range(half, a - 1, -1):
            dp[j] = dp[j] or dp[j - a]
    return dp[half]

def subset_sum_to_partition(S, t):
    """SUBSET-SUM -> PARTITION 化約"""
    sigma = sum(S)
    if not (0 <= t <= sigma):
        return False
    doubled = [2 * s for s in S] + [2 * (sigma - 2 * t) + sigma]
    # 構造總和為偶數的實例；以小實例列舉驗證等價性
    return can_partition([2 * s for s in S] +
                         [2 * sigma - 4 * t, sigma])

def partition_to_knapsack(A):
    """PARTITION -> 背包判定化約"""
    sigma = sum(A)
    if sigma % 2:
        return False
    W = V = sigma // 2
    dp = [0] * (W + 1)
    for a in A:
        for j in range(W, a - 1, -1):
            dp[j] = max(dp[j], dp[j - a] + a)
    return dp[W] >= V

# 等價性驗證：小實例暴力比對
from itertools import combinations
def subset_sum_brute(S, t):
    return any(sum(c) == t for r in range(len(S) + 1)
               for c in combinations(S, r))

S, t = [3, 9, 14, 20], 23
print(subset_sum_brute(S, t), can_partition(
    [2 * s for s in S] + [2 * sum(S) - 4 * t, sum(S)]))
print(partition_to_knapsack([3, 1, 1, 2, 2, 1]))  # True

複雜度分析#

分割判定 DP：O(n·σ) 時間、O(σ) 空間，偽多項式（σ 是數值）。
化約構造本身：僅 O(n) 次算術運算，是「線性時間翻譯」的典範。
PARTITION 的特殊性：雖然 NP-complete，但實務上隨機實例幾乎總是可分割（數字夠多時），這提醒我們 NP-complete ≠ 實例都很難。
化約鏈的方向性：每一節箭頭都是多項式時間、保持解對應，這是 NP-hard 傳遞的直接體現。

練習#

完整實作 SUBSET-SUM → PARTITION 的解還原：給定分割的兩側，輸出原 SUBSET-SUM 的子集。
證明或反駁：若 PARTITION 有 O(n log n) 演算法，則 SUBSET-SUM 也有。（提示：注意化約產生的數字大小。）
生成 n = 10、數字範圍 1~10 的隨機分割實例 100 個，統計可分割比例；再改用數字範圍 1~1000，比較並解釋差異。