多維度背包問題

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

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

數學模型

最大化:  Σ(vᵢ × xᵢ)          ← 最大化總價值
限制條件:
  Σ(wᵢ₁ × xᵢ) ≤ W₁          ← 體積限制
  Σ(wᵢ₂ × xᵢ) ≤ W₂          ← 重量限制
  xᵢ ∈ {0, 1}               ← 每個物品只能選或不選

其中:
  vᵢ = 物品 i 的價值
  wᵢ₁ = 物品 i 的體積
  wᵢ₂ = 物品 i 的重量
  W₁ = 最大體積
  W₂ = 最大重量

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

model = cp_model.CpModel()
n = len(items)

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

# 限制
model.Add(sum(items[i][0] * x[i] for i in range(n)) <= max_volume)  # 體積
model.Add(sum(items[i][1] * x[i] for i in range(n)) <= max_weight)   # 重量

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

# 求解
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())}")
    
    selected = [i for i in range(n) 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}")
    
    # 價值密度分析
    print(f"\n價值密度分析（價值 ÷ 資源消耗）：")
    for i in range(n):
        vol, wt, val = items[i]
        density = val / (vol + wt)
        taken = "✅" if i in selected else "❌"
        print(f"  物品 {i}: 密度 = {density:.2f} {taken}")
else:
    print("無可行解")

擴展：三維背包

加入成本維度更接近真實場景：

# (體積, 重量, 成本, 價值)
items_3d = [
    (10, 5, 100, 100),   # 體積10, 重量5, 成本100, 價值100
    (15, 8, 120, 150),
    (8, 3, 60, 80),
    (20, 12, 180, 200),
]

max_vol, max_wt, max_cost = 30, 15, 300

# 加入第三維限制
model.Add(sum(items_3d[i][2] * x[i] for i in range(len(items_3d))) <= max_cost)

應用場景

1. 貨車裝載

在同時受體積（貨櫃容量）和重量（軸重限制）限制下，最大化貨物價值。

2. 雲端資源分配

在 CPU 核心數、記憶體 (GB) 和網路頻寬限制下，最大化可部署的服務數量。

3. 投資組合選擇

在資金預算、風險承受度、流動性需求限制內，選擇最大化期望收益的股票組合。

4. 專案組合管理

在預算 ($)、工程時間 (人月)、策略契合度等限制下選擇要投資的專案。

總結

MDKP 將背包問題擴展到多個資源維度
強 NP-hard — 沒有偽多項式 DP 解法
CP-SAT 對中小規模問題非常適合
現實資源分配幾乎都是多維度的
3+ 維度同樣可以用 CP-SAT 解決

從一維到多維：背包問題的現實版

基本背包問題只有「重量」一個限制。但真實世界永遠更複雜——你不僅要考慮重量，還要考慮體積、預算、時間等多個維度。

多維度背包的數學模型

最大化：$\sum_{i=1}^{n} v_i x_i$

限制條件：

$\sum_{i=1}^{n} w_i x_i \leq W$（重量限制）
$\sum_{i=1}^{n} s_i x_i \leq S$（體積限制）
$x_i \in {0, 1}$（0/1 限制）

當維度增加時，問題的複雜度急遽上升。一維背包的 DP 是 O(nW)，二維背包就變成 O(nW₁W₂)——維度每加一個，時間就乘上一個容量因子。

真實應用

| 應用 | 維度 | 限制條件 | |:----|:----|:--------| | 伺服器資源分配 | 2-3 | CPU、記憶體、磁碟 | | 廣告預算分配 | 2 | 金額 + 曝光次數限制 | | 工廠生產排程 | 3+ | 原料、工時、機器產能 | | 雲端 VM 選擇 | 4+ | vCPU、RAM、網路、儲存 |

下一章預告：背包問題與選題最佳化

多維度背包讓你看到真實世界的複雜度。下一章回到基本背包問題——但從「選題最佳化」的角度，探討如何在多個專案中選擇最有價值的組合。