C/C++で分枝限定法（Branch and Bound）を用いて0/1ナップサック問題を解く方法

0/1ナップサック問題と分枝限定法

0/1ナップサック問題では、各アイテムを「ナップサックに入れる」か「入れない」かの二者択一で選ばなければなりません。この組み合わせ最適化問題を効率的に解く手法の一つが分枝限定法（Branch and Bound）です。

このアルゴリズムの鍵となるのは、「分数（Fractional）ナップサック問題、つまりアイテムを分割して入れられる問題に対しては、貪欲法が最適解を与える」という性質を活用する点です。探索の過程で生じる各ノードについて、この貪欲法を応用して上限値（バウンド）を求めることで、無駄な探索を切り捨てることができます。

ある特定のノードからより良い解が得られる可能性があるかどうかを調べるには、そのノードを経由した場合の最適解（上限値）を貪欲法で計算します。もし貪欲法によって得られた解が現時点での最良解（best so far）以下であれば、そのノードを深掘りしても改善は見込めないため、そこで探索を打ち切る（枝刈りを行う）ことができます。

アルゴリズムの全体像

完全なアルゴリズムの手順は以下の通りです。

1. アイテムのソート：単位重量あたりの価値（価値÷重みの比率）が高い順にすべてのアイテムを並べ替えます。これにより、貪欲法を用いて上限値を計算できるようになります。

2. 初期化：最大利益を格納する変数を maxProfit = 0 として初期化します。

3. キューの作成：空のキュー Q を生成します。

4. ダミーノードの追加：決定木のルートとなるダミーノードを作成し、キュー Q に挿入（エンキュー）します。ダミーノードの利益と重みはともに 0 です。

5. 探索の繰り返し：キュー Q が空になるまで、以下の処理を繰り返します。

   • キュー Q からノードを1つ取り出します。取り出したノードを u とします。

   • 次のレベルのノードについて、そのアイテムを解に含めた場合の利益を計算します。この利益が maxProfit より大きければ、maxProfit を更新します。

   • 次のレベルのノードについて、上限値（バウンド）を計算します。この上限値が maxProfit より大きい場合は、まだ改善の余地があるため、そのノードをキュー Q に追加します。

   • さらに、次のレベルのアイテムを解に含めないケースも考慮します。この場合は、レベルだけを1つ進めたノード（次のアイテムの重みと利益を加えないノード）をキューに追加します。

実行例

具体的な入力と出力の例を以下に示します。

入力

// 各ペアの最初の値はアイテムの重み
// 2番目の値はアイテムの価値を表す
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10

出力

The maximum possible profit = 235

この例では、重み2・価値40、重み1.98・価値100、重み5・価値95の3つのアイテムを選ぶことで、総重み8.98（容量10以内）となり、最大利益235が達成されます。分枝限定法を使うことで、全数探索を避けながら効率的にこの最適解へたどり着けるのです。