背包問題與選題最佳化

實戰：預算分配

你是一家新創公司的 CTO，有 500 萬的技術預算。面對 10 個可能的技術投資項目，每個項目有不同的成本與預期回報，如何分配預算才能最大化總回報？

from ortools.sat.python import cp_model

# 項目資料
projects = [
    ("AI 客服", 150, 400),
    ("數據平台", 200, 350),
    ("App 開發", 180, 300),
    ("SEO 優化", 50, 180),
    ("績效系統", 120, 250),
    ("自動化測試", 80, 200),
    ("安全稽核", 60, 150),
    ("國際化", 100, 220),
    ("API 平台", 160, 280),
    ("BI 儀表板", 90, 190),
]

budget = 500  # 萬

model = cp_model.CpModel()

x = [model.NewBoolVar(f"x_{i}") for i in range(len(projects))]

# 預算限制
model.Add(sum(projects[i][1] * x[i] for i in range(len(projects))) <= budget)

# 相依性：如果選 AI 客服，必須也選數據平台
model.Add(x[0] <= x[1])

# 互斥：App 開發與 API 平台只能選一個
model.Add(x[2] + x[8] <= 1)

# 目標：最大化回報
model.Maximize(sum(projects[i][2] * x[i] for i in range(len(projects))))

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    print(f"\n=== 預算分配結果 ===")
    print(f"最佳總回報: {int(solver.ObjectiveValue())} 萬")
    print(f"預算上限: {budget} 萬")
    
    total_cost = 0
    for i, (name, cost, ret) in enumerate(projects):
        if solver.Value(x[i]):
            total_cost += cost
            print(f"✅ {name}: 成本 {cost}萬, 回報 {ret}萬")
    print(f"\n總使用預算: {total_cost} 萬")
else:
    print("無法找到最佳解")