雙船裝貨問題：背包問題變體的子集樹窮舉與位運算優化

問題描述

兩艘貨船載重 C1、C2，N 個貨箱重量 W[i]，總重 ≤ C1+C2。求是否存在裝載方案使所有貨箱上船，若有輸出一種方案。

轉化為子集和問題

因總重 ≤ C1+C2，只需找到一個子集裝入船 1 使其重量 ≤ C1，剩餘自動 ≤ C2。即在 [0, C1] 範圍內尋找可行子集和。

子集樹窮舉模型

每個貨箱兩種選擇：裝入船 1 (左分支, 1) 或不裝 (右分支, 0)。N 個貨箱構成高度 N 的二叉樹，葉子節點對應所有 2^N 種裝載方案。遍歷根到葉路徑即可得到一種選擇。

位運算優化窮舉

將選擇方案編碼為 N 位整數 mask (0 ~ 2^N-1)：

• 第 i 位為 1 → 第 i 個貨箱裝入船 1
• 遍歷 mask 從 2^N-1 遞減至 0
• 內層循環右移 mask 並累加對應重量
• 剪枝：累加超過 C1 立即跳出內層循環

核心算法代碼

#include 
#include 

void search(int *weights, int n, int C1, int C2) {
    int total = 0;
    for (int i=0; i= 0; mask--) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                sum += weights[i];
                if (sum > C1) { sum = -1; break; } // 剪枝
            }
        }
        if (sum >= 0 && sum <= C1 && (total - sum) <= C2) {
            printf("方案 mask=%x: ", mask);
            for (int i=0; i

複雜度分析

時間：O(N * 2^N)，N ≤ 20 可接受，N > 25 需動態規劃/分支限界
空間：O(N)


進階優化方向

動態規劃：dp[w] 記錄達到重量 w 的方案掩碼，O(N*C1)，適用大 N 小 C1
分支限界：按重量降序排列，計算剩餘最大可能和剪枝
會合中間：N=40 時分兩半各 2^20 枚舉，再雙指針合併