排箱問題 Bin Packing

排箱問題是組合最佳化中最經典的問題之一。想像你是一家搬家公司的老闆，你有一堆不同大小的箱子要裝進卡車。如何用最少的卡車裝完所有箱子？

這就是 Bin Packing 問題。

安裝 OR-Tools

pip install ortools

使用 CP-SAT 求解排箱問題

from ortools.sat.python import cp_model

# 物品清單（每個物品的體積）
items = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
bin_capacity = 100  # 每個箱子的容量

num_items = len(items)
num_bins = num_items  # 最多需要跟物品數量一樣多的箱子

model = cp_model.CpModel()

# 變數：x[i][b] = 1 表示物品 i 放入箱子 b
x = [[model.NewBoolVar(f'x_{i}_{b}') for b in range(num_bins)] 
     for i in range(num_items)]

# 變數：y[b] = 1 表示箱子 b 被使用
used = [model.NewBoolVar(f'y_{b}') for b in range(num_bins)]

# 限制 1：每個物品必須放入恰好一個箱子
for i in range(num_items):
    model.Add(sum(x[i][b] for b in range(num_bins)) == 1)

# 限制 2：每個箱子的總體積不能超過容量
for b in range(num_bins):
    model.Add(sum(items[i] * x[i][b] for i in range(num_items)) <= bin_capacity)

# 限制 3：如果箱子 b 被使用，則至少有一個物品在其中
for b in range(num_bins):
    model.Add(sum(x[i][b] for i in range(num_items)) >= used[b])
    model.Add(sum(x[i][b] for i in range(num_items)) <= num_items * used[b])

# 目標：最小化使用的箱子數量
model.Minimize(sum(used))

# 求解
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"\n=== 排箱結果 ===")
    print(f"使用箱子: {int(solver.ObjectiveValue())} 個")
    
    for b in range(num_bins):
        if solver.Value(used[b]):
            bin_items = [i for i in range(num_items) if solver.Value(x[i][b])]
            bin_volume = sum(items[i] for i in bin_items)
            print(f"\n箱子 {b}: 總體積 {bin_volume}/{bin_capacity}")
            print(f"  物品: {bin_items}")
            print(f"  體積: {[items[i] for i in bin_items]}")
else:
    print("找不到可行解")

貪婪演算法（大規模問題）

當物品數量超過 100 時，CP-SAT 會變得非常慢。這時使用貪婪啟發式演算法：

First-Fit Decreasing (FFD)

def first_fit_decreasing(items, capacity):
    """將物品從大到小排序，每個放入第一個能裝下的箱子"""
    bins = []  # 記錄每個箱子的剩餘容量
    for item in sorted(items, reverse=True):
        placed = False
        for i, remaining in enumerate(bins):
            if remaining >= item:
                bins[i] -= item
                placed = True
                break
        if not placed:
            bins.append(capacity - item)
    return len(bins)

items = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
print(f"FFD 使用箱子: {first_fit_decreasing(items, 100)}")

Best-Fit Decreasing (BFD)

def best_fit_decreasing(items, capacity):
    """從大到小排序，每個放入剩餘空間最小的箱子"""
    bins = []
    for item in sorted(items, reverse=True):
        best_idx = -1
        best_remaining = capacity + 1
        for i, remaining in enumerate(bins):
            if remaining >= item and remaining - item < best_remaining:
                best_idx = i
                best_remaining = remaining - item
        if best_idx >= 0:
            bins[best_idx] -= item
        else:
            bins.append(capacity - item)
    return len(bins)

print(f"BFD 使用箱子: {best_fit_decreasing(items, 100)}")

演算法比較

| 演算法 | 本例箱數 | 時間 | 近似比 | |-------|---------|------|--------| | CP-SAT（最佳解） | 4 | ~1秒 | 100% | | First-Fit Decreasing | 4 | ~1ms | ≤ 11/9 × OPT | | Best-Fit Decreasing | 4 | ~1ms | ≤ 11/9 × OPT | | Next-Fit | 6 | ~0.1ms | ≤ 2 × OPT |

時間複雜度

| 演算法 | 時間 | |-------|------| | CP-SAT（最佳解） | 指數級（NP-hard），但 <50 物品很快 | | First-Fit Decreasing | O(n log n + n × bins) | | Best-Fit Decreasing | O(n log n + n × bins) | | Next-Fit | O(n) |

總結

排箱問題 = 用最少箱子裝完所有物品
NP-hard — 大規模問題無法在多項式時間內求解
CP-SAT 適用於小到中型（< 50 物品）可求最佳解
FFD/BFD 提供接近最佳的解（11/9 ≈ 1.22 倍近似比）
應用: 雲端 VM 放置、物流裝載、倉庫管理、記憶體分配

排箱問題不只是在搬家

排箱問題（Bin Packing）聽起來像是物流業才需要關心的問題。但實際上，它在軟體工程中無所不在：

雲端伺服器資源分配：把不同大小的容器裝進有限的實體主機
廣告投放：在有限的廣告版位中塞入最多的廣告
影片壓縮：將不同大小的資料區塊放入固定大小的 frame
記憶體管理：作業系統將程式分配到記憶體分頁
資料庫儲存：將資料記錄分配到固定大小的資料頁

下一章預告：從排箱到排程

排箱問題關心的是「如何把東西塞進箱子」。下一章的 工作排程 (Job Scheduling) 關心的是「如何在時間軸上安排好工作順序」——更接近你在日常工作中遇到的排程問題。