排箱問題 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("找不到可行解")

更多章節內容持續建置中...