0-1ナップサック問題 : 分枝限定法

問題. 0-1ナップサック問題(0-1 Knapsack Problem)

$n$ 個のアイテムからなる集合が与えられる． $i$ 番目のアイテムは価値 $v_i$ と重さ $w_i$ を持っている．アイテムをいくつか選び，重み和が $W$ 以下で価値の和が最大となるようなものを選べ．

例） $n = 5, W = 6$

	1	2	3	4	5
価値 [円]	7	8	3	4	5
重さ [kg]	3	5	2	3	4

商品1, 4 を選ぶと重み和は $3 + 3 \le 6$ となり条件を満たし，価値の和は 11 と最大になります．

問題の概要

0-1ナップサック問題の各アイテムがちょうど1つずつではなく，制限が無い場合はナップサック問題と言い，これらの問題はNP困難問題であることが知られています．0-1ナップサック問題の厳密解法としては動的計画法を用いた擬似多項式時間アルゴリズムが有名ですが，ここでは分枝限定法を用いた解法を紹介します．

解法. 分枝限定法（Branch and Bound）

まず始めに0-1ナップサック問題を整数計画問題として定式化します．

整数計画問題 (P)
　maximize　 $\sum_{i = 1}^{n} x_i v_i$
　subject to　 $\sum_{i = 1}^{n} x_i w_i \le W$
　　　　　　 $x_i \in \{0, 1\}$ 　 $(i = 1, 2, \ldots, n)$

変数 $x_i$ は値が $1$ のとき $i$ 番目のアイテムを選択し， $0$ のとき選択をしないことに対応しています．
分枝限定法は変数の値を順番に0か1かに固定していき分枝木を探索していきます．探索の途中で変数 $x_i$ の値を決めるときに， $x_1, x_2, \ldots, x_{i-1}$ の値はは 0 または 1 に固定されています．このとき， $W_i := \sum_{j=1}^{i-1} x_j w_j$ , $V_i := \sum_{j=1}^{i-1} x_j v_j$ とすると， $x_i$ から変数の値を決めることは次の問題を解くことに等しく (P) の部分問題となります．ちなみに，変数の値を固定して部分問題を生成する操作を分枝操作（branching operation）と呼びます．

(P) の部分問題 $(\rm{P}_i)$
　maximize　 $V_i + \sum_{j=i}^{n} x_j v_j$
　subject to　 $\sum_{j=i}^{n} x_j w_j \le W - W_i$
　　　　　　 $x_j \in \{0, 1\}$ 　 $(j = i, i + 1, \ldots, n)$

分枝木の葉は(P) の許容解に対応するのですが，葉の数は $2^n$ 個もあるので分枝木を全探索することはしたくありません．そこで，変数 $x_i$ の部分問題 $(\rm{P}_i)$ を解く必要があるのかをある基準で判定して探索する頂点数を減らすことを考えます．ここでは緩和問題を用いて判定します． $(\rm{P}_i)$ も0-1ナップサック問題なのでここでは (P) を考えることにします．
(P) の緩和問題は次のようになります．

線形計画緩和問題 (LP)
　maximize　 $\sum_{i = 1}^{n} x_i v_i$
　subject to　 $\sum_{i = 1}^{n} x_i v_i \le W$
　　　　　　 $0 \le x_i \le 1$ 　 $(i = 1, 2, \ldots, n)$

各変数 $x_i$ は0以上1以下の実数となり (LP) は線形計画問題となります．(LP) は (P) の許容領域を含むので最大化問題の場合は，
　　(P) の最適値 $\le$ (LP) の最適値
となります．よって，今までで得られた最良値を $v^*$ としたときに，
　　(LP)の最適値 $\le v^*$
ならば，(P) を解いても $v^*$ より大きい値を得ることができないので (P) を解く必要がありません．このように，分枝木の子孫の探索を省略することを限定操作（bounding operation）と呼びます．ちなみに，(LP) の最適解が整数解ならば(P)の最適解となっているので子孫の探索をする必要はありません．
一般に線形計画問題は変数の数と制約式の数に関して多項式時間アルゴリズムとなり，CPLEXやGurobiなどのソルバーを用いて解くのが普通なのですが，(LP) は計算時間 $O(n)$ のソルバーを用いないアルゴリズムが知られています．ここでは， $O(n \log n)$ のアルゴリズムを紹介しますが気になる方はコルテ，フィーゲンの組合せ最適化の本を参考にして下さい．

(LP) を解くアルゴリズム : (ALG)
ステップ1. $n$ 個のアイテムを $v_i / w_i$ の大きい順に並び替え， $v_{i_{1}} / w_{i_{1}} \ge v_{i_{2}} / w_{i_{2}} \ge \cdots \ge v_{i_{n}} / w_{i_{n}}$ とする．
ステップ2. $w := 0, k := 0$ とする．
ステップ3. $k := k + 1$ とする．
ステップ4. $w + w_{i_{k}} \le W$ なら $x_{i_{k}} := 1$ としてステップ3に戻る．それ以外は $x_{i_{k}} := (W - w) / w_{i_{k}}$ とする．
ステップ5. $x_{i_{k+1}}, x_{i_{k+2}}, \ldots, x_{i_{n}}$ の値を0にする．

(ALG) はステップ1のソートにかかる時間が支配的となり計算時間は $O(n \log n)$ となりますが，分枝限定法では(ALG)のステップ1を前処理で行うことによって各限定操作の緩和問題を解く計算時間は $O(n)$ となります．
上の0-1ナップサック問題の例では順番に $v_{i} / w_{i}$ の大きい順に並んでいるので1番目のアイテムから選択していくと， $(x_1, x_2, x_3, x_4, x_5) = (1, 3/5, 0, 0, 0)$ となり，最適値は 11.8 となります．

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

// ------------------------------------------8<------- start of library -------8<----------------------------------------------
template<class T>
class Knapsack {
public:
    const int size;
    vector<bool> opt_item;
    T capacity, opt_v;

    Knapsack(const int _n, const T _c) :
        size(_n), opt_item(_n, false), capacity(_c), n(0), item(_n), used(_n, false) {}
    void add_item(const int v, const int w) {
        item[n].v = v;
        item[n++].w = w;
    }

    T MaximumValue() {
        sort(item.begin(), item.end(),
             [](const Item &d1, const Item &d2) { return d1.v * d2.w > d2.v * d1.w; });

        opt_v = 0;
        for (int i = 0, w = 0; i < size; ++i) {
            if (w + item[i].w <= capacity) {
                w += item[i].w;
                opt_v += item[i].v;
                opt_item[i] = true;
            }
        }

        Rec(0, 0, 0);

        return opt_v;
    }

private:
    struct Item { T v , w; };
    int n;
    vector<Item> item;
    vector<bool> used;

    void Rec(int idx, T value, T weight) {
        if (idx == size || capacity <= weight) {
            if (weight <= capacity && opt_v < value) {
                opt_v = value;
                opt_item = used;
            }
            return ;
        }
        if (opt_v < value) {
            opt_v = value;
            opt_item = used;
        }

        // 線形緩和したときの目的関数値の計算
        double tmp_v = value, tmp_w = weight;
        int tmp_i;
        for (tmp_i = idx; tmp_w < capacity && tmp_i < size; ++tmp_i) {
            if (tmp_w + item[tmp_i].w <= capacity) {
                tmp_v += item[tmp_i].v;
                tmp_w += item[tmp_i].w;
            }
            else if (tmp_w + item[tmp_i].w == capacity) {
                // 緩和解が元の実行可能解
                tmp_v += item[tmp_i].v;
                if (opt_v < tmp_v) {
                    opt_v = tmp_v;
                    opt_item = used;
                    for (int i = idx; i <= tmp_i; ++i)
                        opt_item[i] = true;
                }
                return ;
            }
            else {
                tmp_v += item[tmp_i].v * (capacity - tmp_w) / item[tmp_i].w;
                tmp_w = capacity;
            }
        }
        if (tmp_v <= opt_v) return;

        if (weight + item[idx].w <= capacity) {
            used[idx] = true;
            Rec(idx + 1, value + item[idx].v, weight + item[idx].w);
            used[idx] = false;
        }

        Rec(idx + 1, value, weight);
    }
};
// ------------------------------------------8<------- end of library -------8<----------------------------------------------


int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    // AOJ DPL_1_B 問題
    int n, cap, w, v;

    cin >> n >> cap;
    Knapsack<int> kp(n, cap);
    for (int i = 0; i < n; ++i) {
        cin >> v >> w;
        kp.add_item(v, w);
    }

    cout << kp.MaximumValue() << endl;

    return 0;
}

まとめ

分枝限定法は最悪の場合指数時間必要となりますが，だいたいのインスタンスで限定操作が上手く働き高速に解くことができます．次のリンク先で問題を解いたのですがが1つのインスタンスでTLEとなりました．
0-1 Knapsack Problem | Aizu Online Judge
緩和問題が線形時間で解けるのは嬉しいですね．