固定容量的箱子最少用幾個：從搬家打包到雲端 VM 調度，以及「先放大件」的智慧

顯然的下界

\[OPT \;\geq\; \left\lceil \frac{\sum_i s_i}{C} \right\rceil\]

體積總量除以箱容量，無條件進位。評估任何解時先算它，常常立刻知道「已經最優」。

三個線上/離線演算法

Next Fit（NF）：只看手上這箱

裝不下就封箱開新的，永不回頭。\(O(n)\)、串流可用。保證 \(NF \leq 2\cdot OPT\)：任兩個相鄰箱子的總和 \(> C\)（否則不會開新箱），所以箱數 \(< 2\sum s_i / C \leq 2\,OPT\)。

First Fit（FF）：掃全部箱子

放進第一個裝得下的箱子。\(O(n\log n)\)（用平衡樹找箱）。保證 \(FF \leq \lceil 1.7\,OPT\rceil\)。

First Fit Decreasing（FFD）：先排序再 FF

物品由大到小排序後跑 FF。

直覺：大件是「地形」，先擺定；小件是「沙子」，往縫裡流。反過來先撒沙子，地形就擺不進去了——Example 2 的實測正是這個劇本。

手算範例

物品 \(\{4,8,1,4,2,1\}\)、\(C=10\)、下界 \(\lceil 20/10\rceil = 2\)：

（NF 的細節：\(4\) 進箱 1；\(8\) 裝不下封箱開箱 2；\(1\) 進箱 2；下一個 \(4\) 裝不下箱 2（剩 1），開箱 3……NF 的痛點是封掉的箱子有縫也回不去。）

FFD 也有極限

FFD 不是精確演算法。本篇程式 Example 3 的實例（總和 300、\(C=100\)、下界 3）FFD 用了 4 箱、精確解 3 箱：FFD 把 \(51+30\) 裝在一起浪費了 19 的縫，而最優解需要「刻意不貪」的組合（如 \(51+27+22\)、\(50+50\)、\(26+23+21+30\)）。要精確就得回溯搜尋（程式附帶剪枝版：大件先放 + 相同剩餘空間的箱只試一個 + 箱數超過已知最佳就砍）。

完整 C++ 程式

包含：NF、FF、FFD（含每箱內容輸出）、下界計算、回溯精確解（對稱剪枝）、100 隨機實例統計。編譯：

g++ -std=c++17 -O2 -Wall -Wextra -o bin_packing bin_packing.cpp

執行結果與解讀

=== Example 1: NF vs FF vs FFD ===
items {4,8,1,4,2,1}, capacity 10, lower bound = 2
NextFit : 3 bins   [4] [8,1] [4,2,1]
FirstFit: 2 bins   [4,1,4,1] [8,2]
FFD     : 2 bins   [8,2] [4,4,1,1]

=== Example 3: FFD is not optimal either ===
items sum=300, capacity 100, lower bound = 3
FFD   bins = 4     [51,30] [50,50] [27,26,23,22] [21]
exact bins = 3 (nodes=26)

=== Example 4: FFD quality on random instances ===
100 random instances (12 items, size 10-70, cap 100):
FFD optimal 91/100 times, avg FFD=5.52 vs avg OPT=5.43
theory: FFD <= (11/9) OPT + 6/9, in practice usually spot-on

實務應用

• 雲端 VM 調度：把工作負載（CPU/RAM 需求）塞進最少的實體機——Kubernetes 調度器的 bin-packing 策略、AWS 的容量規劃。裝越密，電費省越多。

• 物流裝櫃：貨櫃、卡車、棧板的裝載規劃（實務是二維/三維變形）。

• 廣告排期：時段長度固定，廣告長短不一，最少用幾個時段播完。

• 記憶體配置：allocator 的 slab/區塊管理本質是線上裝箱。

• 裁切問題：鋼材、布料、玻璃的下料切割（cutting stock，同構問題）。

練習題

1. 手算 \(\{7,5,6,4,2,3,7,2\}\)、\(C=12\)：下界、NF、FF、FFD 各多少？

2. 實作 Best Fit（放進「剩餘空間最小且裝得下」的箱）與 Worst Fit，加入 Example 4 的統計擂台。

3. 構造一個 FF 比 FFD 差至少 2 箱的實例。

4. 線上情境（物品逐一到達、不可重排）NF 與 FF 都合法，FFD 不行——為什麼？線上演算法的競爭比下界是多少（查 1.54…）？

5. 挑戰：把精確解加上「下界剪枝」（剩餘體積除以容量進位 + 已用箱數 \(\geq\) 已知最佳即砍），實測能解到幾件物品。

小結

延伸閱讀：Johnson (1973) 博士論文（FF/FFD 首次分析）；Dósa (2007) FFD 緊界；Coffman, Garey & Johnson 的裝箱綜述；Karmarkar–Karp (1982) 漸近 PTAS。