Day 150-Q3 — 分枝限定法（Branch and Bound・0/1ナップサック問題）

2026-09-11 赤色 Master / Phase 8+ ★★★★★★★★★ フラクショナル緩和の上界で「これ以上探索しても更新不可能」な部分木を丸ごと切り捨てる

問題

$N$個の品物（品物$i$は重さ$w_i$、価値$v_i$）と容量$W$のナップサックが与えられる。重さの合計が$W$を超えない範囲で価値の合計を最大化する、その最大価値と、探索中にDFS再帰関数が呼び出された回数（打ち切られたノードも1回とカウント）を求めよ。

探索手順

  1. 品物を「価値/重さ比」降順（同値は元インデックス昇順）に並べ替える。
  2. dfs(i, cur_weight, cur_value) の呼び出しごとにノードを1つ消費。
  3. cur_weight > W なら終了。cur_valueで最良価値を更新。i==Nなら終了。
  4. 上界 = cur_value + $i$番目以降をフラクショナルに詰めた価値。上界 $\le$ 最良価値なら打ち切り。
  5. 打ち切られなければ「含める」を先に、次に「含めない」を探索。

入力形式

N W
w_1 v_1
:
w_N v_N

制約

$1 \le N \le 15$
$1 \le W \le 100$
$1 \le w_i, v_i \le 100$

入出力例

入力例1

5 10
2 3
3 4
4 5
5 8
9 10

出力例1

15 7

概念図：実際に探索される7ノードの木

ソート順: 品物4(比1.6) > 品物1(1.5) > 品物2(1.333) > 品物3(1.25) > 品物5(1.111) #1 bound15.0 #2 +4 v=8 bound15.0 #7 -4 pruned 13.1≤15 #3 +1 v=11 bound15.0 #6 -1 pruned 14.5≤15 #4 +2 v=15 best更新 bound15.0≤15 pruned #5 -2 v=11 pruned 14.8≤15 緑実線=include分岐、赤破線=exclude分岐。全7ノードのうち#4で最適値15を達成し、以後は全て枝刈り。

ヒント（段階的開示）

ヒント1（方向性）

全探索は$2^N$通り全てを試すが、分枝限定法は「この先どんなに頑張っても現在の最良解を超えられない」と判定できた枝を、実際には1つも展開せずに切り捨てる。上界が甘いと枝刈りが効かず全探索とほぼ同じになる。

ヒント2（アプローチ）

上界を計算するときだけ「一部だけ入れる（フラクショナル）」を許すと、貪欲法で厳密な最適値が高速に求まる。この値は0/1の場合の真の最適値より必ず大きいか等しいため、安全な上界として使える。

ヒント3（誘導） 
order = sorted(items, key=lambda it: (-it.value/it.weight, it.index))

def bound(i, cur_weight, cur_value):
    rem = W - cur_weight
    val = cur_value
    for j in range(i, N):
        w, v = order[j].weight, order[j].value
        if w <= rem:
            rem -= w; val += v
        else:
            val += v * (rem / w); break
    return val

模範解答 (Python)

import sys


def main():
    data = sys.stdin.read().split()
    ptr = 0
    n = int(data[ptr]); w_cap = int(data[ptr + 1]); ptr += 2
    items = []
    for i in range(n):
        w = int(data[ptr]); v = int(data[ptr + 1]); ptr += 2
        items.append((i, w, v))

    order = sorted(items, key=lambda it: (-it[2] / it[1], it[0]))
    N = len(order)

    best_value = 0
    node_count = 0

    def bound(i, cur_weight, cur_value):
        rem = w_cap - cur_weight
        val = cur_value
        for j in range(i, N):
            _, w, v = order[j]
            if w <= rem:
                rem -= w
                val += v
            else:
                val += v * (rem / w)
                break
        return val

    def dfs(i, cur_weight, cur_value):
        nonlocal best_value, node_count
        node_count += 1
        if cur_weight > w_cap:
            return
        if cur_value > best_value:
            best_value = cur_value
        if i == N:
            return
        if bound(i, cur_weight, cur_value) <= best_value:
            return
        _, w, v = order[i]
        dfs(i + 1, cur_weight + w, cur_value + v)
        dfs(i + 1, cur_weight, cur_value)

    dfs(0, 0, 0)
    print(best_value, node_count)


main()

Step-by-Step 解説

1価値/重さ比でソート
品物は(4,5,8,1.6) (1,2,3,1.5) (2,3,4,1.333) (3,4,5,1.25) (5,9,10,1.111)の順（元インデックス表記）。
2根の上界
bound(0,0,0)は容量10を比の高い順に詰めた理論値で、品物4,1,2をちょうど詰め切れて端数なし＝15.0。
3include優先で早期に強い解を得る
#4ノード（+4+1+2）で価値15に到達し最良解を更新、直後にbound15.0≤15で打ち切られる。
4ノード数で効果を確認
分枝限定法は7ノードしか訪問しないが、上界枝刈りなし(重さ超過のみで打ち切り)だと57ノードかかる。同じ最適値15を得るのに訪問数が約1/8。

よくあるミス

ミス原因正しい書き方
上界比較を<にして同値でも続行「同じなら改善余地あり」と誤解bound <= best_valueで打ち切る
ソート基準を逆（重さ/価値）にする比の定義の取り違え「価値/重さ」が大きい順にソート
打ち切られたノードをカウントし忘れる子展開時のみカウント関数呼び出しの先頭で必ずカウント
include/excludeの呼び出し順を逆にする順序が結果に影響しないと誤解枝刈りの発火タイミングが変わりノード数が変化する。問題文の順序を厳守
フラクショナル上界で端数を切り捨てる整数価値のみ加算端数分の価値v*(rem/w)も上界に加える

次のステップ

  • 発展: 動的計画法による「残り容量ごとの理論的最大価値テーブル」を上界に使うと、フラクショナル緩和よりさらに強い枝刈りが可能になる場合がある。
  • 次回予告: タブーサーチ（Tabu Search・巡回セールスマン問題の2-opt近傍探索）

自己評価

自分の回答

気づき・メモ