背包問題與選題最佳化

實戰：預算分配

你是一家新創公司的 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("無法找到最佳解")

擴展：投資組合最佳化

同樣的模型可應用於股票選擇：

# 股票資料
stocks = [
    ("AAPL", 180, 0.25),  # (名稱, 股價, 預期報酬率)
    ("GOOGL", 140, 0.20),
    ("MSFT", 330, 0.22),
    ("AMZN", 150, 0.30),
    ("TSLA", 250, 0.35),
]

max_investment = 1000  # $1M

# 精選 3 支股票
model.Add(sum(x[i] for i in range(len(stocks))) == 3)

# 單支股票不超過 60%
for i in range(len(stocks)):
    model.Add(stocks[i][1] * x[i] <= max_investment * 0.6)

其他應用場景

| 場景 | 說明 | |------|------| | 人員招募 | 預算內選擇最佳候選人組合 | | 廣告投放 | 預算限制下選擇最高 ROI 的渠道 | | 產品開發 | 有限資源下選擇最具影響力的功能 | | 庫存採購 | 資金限制內選購最佳商品組合 |

總結

| 面向 | 詳情 | |------|------| | 問題 | 預算內選擇項目以最大化回報 | | 限制類型 | 預算、相依性、互斥、數量下限 | | CP-SAT | 自然處理所有限制類型 | | ROI 分析 | 從求解結果自動計算 | | 擴展 | 投資組合、招募、資源分配 |

組合最佳化課程完成！🎉

✅ 排箱問題
✅ 工作排程
✅ 多維度背包
✅ 2D 切割
✅ 預算分配
✅ 相依性與互斥限制
✅ 投資組合最佳化

背包問題：有限資源下的最佳選擇

背包問題（Knapsack）是最經典的 NP-hard 問題之一。想像你有一個背包，容量有限，你要從一堆物品中選出總價值最高的組合。

背包問題的變體

| 類型 | 限制 | 解法 | |:----|:----|:----| | 0/1 Knapsack | 每個物品只能選或不選 | DP：O(nW) 偽多項式時間 | | Fractional Knapsack | 物品可以分割 | 貪婪：按價值/重量比排序 | | Unbounded Knapsack | 每個物品可以取無限次 | DP：O(nW) | | Multi-dimensional | 多個限制條件（重量+體積） | DP：O(nW₁W₂) |

在真實世界的應用

廣告投放：有限預算下選擇最高轉換率的廣告組合
投資組合：有限資金下選擇最佳報酬的投資標的
資源分配：有限伺服器資源下選擇要執行的任務
物流裝載：有限載重下裝載最高價值的貨物

課程總結

這堂組合最佳化課你學到了排箱、排程、TSP、Cutting & Packing 和背包問題——五個最經典的 NP-hard 問題。每個問題都有對應的 CP-SAT 精確解法或啟發式近似演算法，你可以根據問題規模選擇適合的策略。