切割與包裝問題

工業切割問題是排箱問題的變體：

• 鋼鐵廠：如何切割鋼板才能讓廢料最少？
• 服裝廠：如何在布料上排列版型才能最省布？
• 木工廠：如何切割木板才能得到最多的成品？

2D 排箱 (2D Bin Packing)

from ortools.sat.python import cp_model

# === 矩形物品 ===
rectangles = [
    (3, 2),   # 物品 0
    (4, 3),   # 物品 1
    (2, 2),   # 物品 2
    (5, 2),   # 物品 3
    (3, 3),   # 物品 4
    (2, 4),   # 物品 5
    (4, 2),   # 物品 6
    (3, 4),   # 物品 7
]

bin_width = 10
bin_height = 10

num_items = len(rectangles)

model = cp_model.CpModel()

# 每個物品的位置與旋轉
x = [model.NewIntVar(0, bin_width, f"x_{i}") for i in range(num_items)]
y = [model.NewIntVar(0, bin_height, f"y_{i}") for i in range(num_items)]

# 是否旋轉
rotated = [model.NewBoolVar(f"rot_{i}") for i in range(num_items)]

# 寬與高（考慮旋轉）
w = [model.NewIntVar(0, bin_width, f"w_{i}") for i in range(num_items)]
h = [model.NewIntVar(0, bin_height, f"h_{i}") for i in range(num_items)]

for i in range(num_items):
    # 如果旋轉則寬高交換
    model.Add(w[i] == rectangles[i][0]).OnlyEnforceIf(rotated[i].Not())
    model.Add(w[i] == rectangles[i][1]).OnlyEnforceIf(rotated[i])
    model.Add(h[i] == rectangles[i][1]).OnlyEnforceIf(rotated[i].Not())
    model.Add(h[i] == rectangles[i][0]).OnlyEnforceIf(rotated[i])
    # 在邊界內
    model.Add(x[i] + w[i] <= bin_width)
    model.Add(y[i] + h[i] <= bin_height)

# 物品不重疊（使用 NoOverlap2D）
intervals_x = [model.NewIntervalVar(x[i], w[i], x[i] + w[i], f"ix_{i}") 
               for i in range(num_items)]
intervals_y = [model.NewIntervalVar(y[i], h[i], y[i] + h[i], f"iy_{i}")
               for i in range(num_items)]
model.AddNoOverlap2D(intervals_x, intervals_y)

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

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"\n=== 2D 排箱結果 ===")
    for i in range(num_items):
        rx = solver.Value(x[i])
        ry = solver.Value(y[i])
        rw = solver.Value(w[i])
        rh = solver.Value(h[i])
        rot = "旋轉" if solver.Value(rotated[i]) else ""
        print(f"物品 {i} ({rectangles[i]}): ({rx},{ry}) → ({rx+rw},{ry+rh}) {rot}")
    
    # 計算使用率
    total_area = bin_width * bin_height
    used_area = sum(rw * rh for i in range(num_items)
                    for rw, rh in [(solver.Value(w[i]), solver.Value(h[i]))])
    print(f"\n板材面積: {total_area}")
    print(f"使用面積: {used_area}")
    print(f"使用率: {used_area/total_area:.1%}")
else:
    print("找不到可行排法")