Day 040-Q5 — 多次元ナップサック LP 緩和 + ランダム化丸め

2026-05-23 赤色 Master / Phase 8+ ★★★★★★★★★ LP Relaxation + Randomized Rounding

問題

$N$ 個のアイテムと $D$ 次元の容量制約がある多次元ナップサック問題。アイテム $i$ は価値 $v_i$、各次元 $d$ の重さ $w_{i,d}$ を持つ。以下を求めよ：

  1. LP 緩和解（$x_i \in [0,1]$）の最適値
  2. LP 解を用いたランダム化丸めを $T$ 回繰り返し、実行可能かつ最大の整数解

制約

$1 \le N \le 50$
$1 \le D \le 5$
$1 \le T \le 100$
$1 \le v_i, w_{i,d}, C_d \le 500$
時間制限: 3sec / メモリ: 256MB

入出力例

入力例 1

4 2 100
10 6 12 8
2 3
1 2
4 1
3 2
6 5

出力例 1

22

最適解: アイテム1+3を選択 → 価値10+12=22、制約: 2+4=6≤6, 3+1=4≤5

概念図: LP 緩和からランダム化丸めへのフロー

LP 緩和 x_i ∈ [0, 1] x* = [0.8, 0.2, 1.0, 0.5] T 回繰り返し ランダム化丸め P(x_i=1) = x_i* x = [1, 0, 1, 0] など 実行可能？ 最大値記録 制約チェック OK best = max(best, val) LP 緩和の定式化（scipy.optimize.linprog 使用） maximize: Σ v_i * x_i s.t. Σ_i w_{i,d} * x_i ≤ C_d ∀d ∈ {1,...,D} 0 ≤ x_i ≤ 1 ∀i → linprog(-v, A_ub=W.T, b_ub=C, bounds=[(0,1)]*N) LP 最適値 ≥ 整数最適値（緩和なので上界） ランダム化丸めは近似解: 実行可能解のみ採用

ヒント（段階的開示）

ヒント1: LP 緩和の意味
整数制約 $x_i \in \{0,1\}$ を $x_i \in [0,1]$ に緩和すると線形計画問題になり多項式時間で解ける。LP 最適値は整数最適値の上界。
ヒント2: ランダム化丸めのアイデア
LP 解 $x_i^* \in [0,1]$ を各 $x_i$ が 1 になる確率として使う。独立にサンプリングして実行可能解を T 回生成し最大値を採用。制約を破る場合はその解を棄却。
ヒント3: scipy を使った実装 
from scipy.optimize import linprog
import numpy as np

c = -v  # 最小化 → 最大化
A_ub = W.T  # shape (D, N)
b_ub = C
bounds = [(0, 1)] * N

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')
x_star = result.x  # LP 解 x_i* in [0,1]

# ランダム化丸め
x = [1 if random.random() < x_star[i] else 0 for i in range(N)]
if np.all(W.T @ np.array(x) <= C + 1e-9):
    val = int(v @ np.array(x))

模範解答 (Python)

import sys
import random
import numpy as np
from scipy.optimize import linprog
input = sys.stdin.readline

def solve():
    N, D, T = map(int, input().split())
    v = list(map(int, input().split()))
    W = []
    for _ in range(N):
        W.append(list(map(int, input().split())))
    C = list(map(int, input().split()))

    v = np.array(v, dtype=float)
    W = np.array(W, dtype=float)  # shape (N, D)
    C = np.array(C, dtype=float)

    # LP 緩和: maximize v@x s.t. W.T @ x <= C, 0<=x<=1
    c = -v
    A_ub = W.T  # shape (D, N)
    b_ub = C
    bounds = [(0, 1)] * N

    result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

    if result.success:
        x_star = result.x
    else:
        x_star = np.ones(N) * 0.5  # フォールバック

    # ランダム化丸め T 回
    best = 0
    for _ in range(T):
        x = np.array([1 if random.random() < x_star[i] else 0 for i in range(N)])
        usage = W.T @ x
        if np.all(usage <= C + 1e-9):
            val = int(v @ x)
            if val > best:
                best = val

    # 貪欲（保険）
    greedy_x = np.zeros(N, dtype=int)
    order = sorted(range(N), key=lambda i: -v[i])
    usage = np.zeros(D)
    for i in order:
        if np.all(usage + W[i] <= C + 1e-9):
            greedy_x[i] = 1
            usage += W[i]
    g_val = int(v @ greedy_x)
    best = max(best, g_val)

    print(best)

solve()

Step-by-Step 解説

1LP 緩和の定式化
整数制約 $x_i \in \{0,1\}$ を $x_i \in [0,1]$ に緩和。これは多項式時間で解ける。LP 最適値 ≥ 整数最適値（緩和なので）。
2scipy.optimize.linprog の使い方
linprog は最小化問題。maximize v@x = minimize -v@x。制約 A_ub @ x <= b_ub に対応。W の形状は (N, D) なので A_ub = W.T (D, N)。
3ランダム化丸めのアイデア
LP 解 $x_i^* \in [0,1]$ を各 $x_i$ が 1 になる確率として使う。独立にサンプリングして実行可能解を T 回生成し最大値を採用。
4実行可能性確保
ランダム丸めで制約を破る場合があるため実行可能性をチェック。破っている場合はその解を棄却（貪欲の保険あり）。
5近似保証
理論的に $D=1$ の場合はランダム化丸めで近似比が保証される。多次元では保証は弱いが実用的。貪欲を保険として組み合わせる。

計算量

LP 解法: $O(N^{2.5} D)$（内点法）
ランダム化丸め 1 回: $O(ND)$
全体: $O(N^{2.5} D + T \cdot ND)$
$N=50, D=5, T=100$ では十分高速

よくあるミス

ミス原因正しい書き方
A_ub の形状ミスW.T を忘れて W のまま使うA_ub = W.T（shape D×N）
最大化を最小化に変換し忘れlinprog は最小化c = -v
浮動小数点誤差で実行可能性チェック失敗<= C のみ<= C + 1e-9
ランダム化丸めで全解が棄却されるT が少ない or LP 解が極端貪欲解を保険として追加

次のステップ

  • 発展: 分枝限定法（Branch and Bound）で多次元ナップサックの厳密解
  • 応用: 半整数丸め（x_i > 0.5 なら 1、else 0）との比較
  • 類題: セットカバー問題の LP 緩和 + ランダム化丸め（O(log n) 近似）

自己評価