多次元ナップサック

🔥 Vibe プロンプト

「多次元ナップサックを解決：アイテム(容積,重量,価値)、最大容積30、最大重量15、総価値を最大化。」

多次元ナップサック問題とは？

多次元ナップサック (MDKP) は、古典的な0/1ナップサックを複数のリソース制約に拡張したものです。現実のリソース配分はほとんどの場合、多次元的です：

| シナリオ | 次元 | |---------|------| | 🚚 トラック積載 | 容積 + 重量 | | ☁️ クラウドVM配置 | CPU + メモリ + 帯域幅 | | 💰 投資ポートフォリオ | 資本 + リスク + 流動性 | | 🏗️ プロジェクト選択 | 予算 + 時間 + 人員 |

数学的定式化

最大化:  Σ(vᵢ × xᵢ)           ← 総価値を最大化
制約:
  Σ(wᵢ₁ × xᵢ) ≤ W₁              ← 容積制約
  Σ(wᵢ₂ × xᵢ) ≤ W₂              ← 重量制約
  xᵢ ∈ {0, 1}                    ← 各アイテムは取るか取らないか

実装

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),
    (6, 4, 60),
    (18, 10, 180),
    (14, 9, 140),
]

max_volume = 30
max_weight = 15

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

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()
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    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)
        mark = "✅" if i in selected else "❌"
        print(f"  アイテム{i}: 密度={density:.2f} {mark}")

3次元ナップサックへの拡張

# (容積, 重量, コスト, 価値)
items_3d = [(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(n)) <= max_cost)

比較: 古典 vs 多次元

| 項目 | 古典0/1ナップサック | 多次元 | |------|--------------------|--------| | 制約数 | 1 (重量) | 2+ (重量、容積、コスト…) | | 複雑さ | NP困難（疑似多項式） | 強NP困難 | | DP可能 | Yes (O(nW)) | No (次元の呪い) | | CP-SAT適合 | Yes | Yes（得意分野！） | | 現実適合度 | 限定的 | 非常に良い |

実世界の応用

1. トラック積載

容積（トレーラー容量）と重量（車軸制限）の両方を考慮して貨物価値を最大化。

2. クラウドリソース配分

CPUコア、メモリ（GB）、ネットワーク帯域幅の制限内でデプロイするサービス数を最大化。

3. 投資ポートフォリオ

資本予算、リスク許容度、流動性要件の制約内で期待リターンを最大化する銘柄を選択。

4. プロジェクトポートフォリオ管理

予算（$）、エンジニアリング時間（人月）、戦略的適合性スコアの制約内で資金提供するプロジェクトを選択。

まとめ

MDKP はナップサックを複数リソース次元に拡張
強NP困難 — 疑似多項式DP解は存在しない
CP-SAT は小〜中規模インスタンスに最適
現実のリソース配分はほとんどの場合多次元的
3+次元もCP-SATで問題なく処理可能（制約を追加するだけ）

多次元ナップサック

🔥 Vibe プロンプト