多維度背包問題

現實中的資源分配很少只有一個維度。例如：

• 貨車配送：同時受限於體積與重量
• 雲端資源分配：同時受限於 CPU、記憶體、頻寬
• 專案管理：同時受限於時間、人力、預算

CP-SAT 多維度排箱

from ortools.sat.python import cp_model

# 物品：每個物品有 (體積, 重量, 價值)
items = [
    (10, 5, 100),   # 物品 0
    (15, 8, 150),   # 物品 1
    (8, 3, 80),     # 物品 2
    (20, 12, 200),  # 物品 3
    (12, 7, 120),   # 物品 4
    (6, 4, 60),     # 物品 5
    (18, 10, 180),  # 物品 6
    (14, 9, 140),   # 物品 7
]

# 箱子容量
max_volume = 30
max_weight = 15

num_items = len(items)

model = cp_model.CpModel()

# 變數：x[i] = 1 表示物品 i 被選中
x = [model.NewBoolVar(f"x_{i}") for i in range(num_items)]

# 限制：總體積不超過
model.Add(sum(items[i][0] * x[i] for i in range(num_items)) <= max_volume)

# 限制：總重量不超過
model.Add(sum(items[i][1] * x[i] for i in range(num_items)) <= max_weight)

# 目標：最大化總價值
model.Maximize(sum(items[i][2] * x[i] for i in range(num_items)))

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

if status == cp_model.OPTIMAL:
    print(f"\n=== 多維度背包結果 ===")
    print(f"最佳價值: {int(solver.ObjectiveValue())}")
    
    selected = [i for i in range(num_items) if solver.Value(x[i])]
    total_vol = sum(items[i][0] for i in selected)
    total_wt = sum(items[i][1] for i in selected)
    
    print(f"選中物品: {selected}")
    print(f"總體積: {total_vol}/{max_volume}")
    print(f"總重量: {total_wt}/{max_weight}")
else:
    print("無解")