貪婪算法經典應用：貨箱裝船問題 C++ 實現與最優性證明

貪婪算法經典應用：貨箱裝船問題 C++ 實現與最優性證明

貨箱裝船問題是貪婪算法的教科書級案例：給定 n 個貨箱，重量 w[i]，船載重上限 c，目標是裝載**最多數量**的貨箱。貪婪策略——**每次選剩餘最輕貨箱**——能保證全局最優。

問題形式化

• 決策變量：x[i] ∈ {0,1}，1 表示裝載第 i 個貨箱
• 約束：Σ w[i]*x[i] ≤ c
• 目標：最大化 Σ x[i]

貪婪策略與示例

策略：按重量升序排序，依次嘗試裝載，直到剩餘容量無法容納下一個最輕貨箱。

例：n=8, w=[100,200,50,90,150,50,20,80], c=400

1. 排序後索引順序：[7(20), 3(50), 6(50), 8(80), 4(90), 1(100), 5(150), 2(200)]
2. 依次裝載：20+50+50+80+90+100 = 390 ≤ 400，剩餘 10 < 下一個 150
3. 結果：x=[1,0,1,1,0,1,1,1]，裝載 6 個貨箱 (最優解)

最優性證明 (交換論證)

1. 設貪婪解 X，任意可行解 Y。證明 |X| ≥ |Y|。
2. 假設貨箱已按重量升序排列：w₁ ≤ w₂ ≤ ... ≤ wₙ。
3. 貪婪解存在分界點 k：xᵢ=1 (i≤k), xᵢ=0 (i>k)。
4. 找最小 j 使 xⱼ ≠ yⱼ。必有 j ≤ k (否則 Y 超重)。
5. 因 xⱼ=1, yⱼ=0，將 yⱼ 置 1。若 Y 變不可行，則存在 l>j 使 yₗ=1。因 wⱼ ≤ wₗ，將 yₗ 置 0 可恢復可行性，且 1 的個數不減少。
6. 重複交換，最終將 Y 轉化為 X，過程中 1 的個數單調不減，故 |X| ≥ |Y|。QED。

C++ 模板實現 (O(n log n))

#include 
#include 

template 
void ContainerLoading(std::vector &x, const std::vector &w, T c) {
    int n = w.size();
    x.assign(n, 0);
    
    // 間接排序：獲得按重量升序的索引數組
    std::vector idx(n);
    std::iota(idx.begin(), idx.end(), 0);
    std::sort(idx.begin(), idx.end(), [&](int i, int j) { return w[i] < w[j]; });
    
    // 貪婪選擇
    for (int i = 0; i < n && w[idx[i]] <= c; ++i) {
        x[idx[i]] = 1;
        c -= w[idx[i]];
    }
}

// 使用示例
int main() {
    std::vector w = {100, 200, 50, 90, 150, 50, 20, 80};
    double c = 400;
    std::vector x;
    ContainerLoading(x, w, c);
    // x = [1,0,1,1,0,1,1,1], sum = 6
    return 0;
}

複雜度分析

• 間接排序：O(n log n) (或堆排序/歸並排序)
• 貪婪掃描：O(n)
• 總體：O(n log n)

擴展思考

• 0-1 背包問題：若目標改為最大化總價值而非數量，貪婪失效，需動態規劃 (O(nc)) 或近似算法。
• 分數背包：允許拆分貨箱，貪婪 (按單位價值排序) 最優。
• 多船調度：推廣為多容器裝箱問題 (Bin Packing)，NP-hard，需啟發式/元啟發式算法。

---

貨箱裝船問題完美展示了貪婪算法「局部最優選擇推導全局最優」的威力，其交換論證證明模板廣泛適用於證明其他貪婪算法的最優性。