C++ DFS 剪枝優化：背包問題剪枝條件深度解析

題目背景

將 N 張分值不同的郵票分成兩堆，使兩堆分值差最小。經典 0/1 背包 / 分割問題。目標：找出一堆分值和最接近總和一半 (V) 的組合。

核心程式碼與剪枝條件

#define max(a,b) a>b?a:b
int V, ans, n, w[110], sum[110]; // V=總和/2, ans=目前最佳解(≤V)

void dfs(int i, int cnt) { // i: 考慮第 i 個物品 (從 n 遞減至 1), cnt: 目前累積和
    if (i == 0) { // 遞歸邊界：所有物品決策完畢
        ans = max(ans, cnt);
        return;
    }
    
    // ========== 關鍵剪枝條件 ==========
    if (ans == V || cnt + sum[i] <= ans) return; 
    // ==================================
    
    if (cnt + w[i] <= V) // 選擇第 i 個物品
        dfs(i - 1, cnt + w[i]);
    dfs(i - 1, cnt); // 不選擇第 i 個物品
}

int main() {
    // ... 輸入 n, w[1..n] ...
    // sum[i] = w[1] + ... + w[i] (前綴和)
    V = sum[n] / 2;
    dfs(n, 0);
    printf("%d\n", sum[n] - 2 * ans); // 總和 - 2*較小堆 = 差值
}

剪枝條件逐項解析

條件一：`ans == V`

• `ans` 記錄「不超過 V 的最大累積和」。
• 若 `ans` 已達到理論上限 `V` (即找到完美分割，兩堆相等)，**後續搜尋毫無意義**，直接返回。

條件二：`cnt + sum[i] <= ans`

• `sum[i]` = 第 1 到第 i 個物品的分值總和 (即**剩餘所有物品的總和**)。
• `cnt + sum[i]` = **即使把剩下所有物品全選上，也只能達到的最大理論值**。
• 若這個理論上限 **≤ 目前最佳解 `ans`**，說明**無論怎麼選，都無法超越現有最佳解**，剪枝返回。
• 這是**上界剪枝** (Bound Pruning)，利用問題單調性 (只加不減) 推導上界。

為何 `sum[i]` 是前綴和而非後綴和？

程式碼中 `i` 從 `n` 遞減至 `1`。`sum[i]` 定義為 `w[1] + ... + w[i]`。當搜尋到第 `i` 層時，**剩餘未決策的物品正是 1~i 號**，其總和即 `sum[i]`。若 `i` 從 1 遞增至 n，則需用後綴和 `suffixSum[i] = w[i] + ... + w[n]`。

搜尋順序影響剪枝效率

• **先搜大分值** (將 `w` 陣列降序排序) 可讓 `ans` 快速增大，觸發更多 `cnt + sum[i] <= ans` 剪枝。
• 本程式碼未顯式排序，假設輸入順序即搜尋順序。實際應用**務必先排序**。

複雜度分析

• 無剪枝：O(2^N) 指數爆炸。
• 有剪枝：實際運行極快，N=100 通常毫秒級完成。屬於**分支限界法** 典型應用。

結論

DFS 剪枝核心在於**計算理論上界**，若上界無法超越當前最佳解，果斷放棄該子樹。`cnt + sum[i] <= ans` 是利用「剩餘資源總和」作為上界的經典技巧，配合 `ans == V` 最優解提前終止，將指數搜尋剪枝至可接受範圍。理解上界推導邏輯，是解決組合優化問題的關鍵能力。