0-1ナップサック問題の分枝限定法による解法
(dp/branch-and-bound.hpp)

• View this file on GitHub
• Last update: 2021-11-25 10:30:05+09:00
• Include: #include "dp/branch-and-bound.hpp"

0-1ナップサック問題の、分枝限定法による解法

概要

0-1ナップサック問題

品物が$N$個(品物$0$から品物$N-1$)あり、品物$i$は価値$v_i$重さ$w_i$である。重さの総和が$W$以下となるようにいくつかの品物を選んだとき、選んだ品物の価値の総和の最大値$V_{\max}$を求めよ。

いくつかの品物について選択が決まったとき、残りの品物で有理ナップサック問題を解いて最適解の上界とする。再帰関数で探索するが、現在のノードでの最適解の上界が既知の解以下になった場合は、その先の探索を行わない（分枝限定法）。

使い方

• BranchAndBound<V,W>(v,w): コンストラクタ。数列$v={v_i}$,$w={w_i}$を与える。計算量$\mathrm{O}(N\log N)$
• run(w): wで値$W$を与える。0-1ナップサック問題の解$V_{\max}$を返す。計算量$\mathrm{O}(2^N)$

注意点

• このライブラリは、弱いテストケースを狙う嘘解法での利用を想定したものである。

Verified with

• verify/verify-aoj-dpl/aoj-dpl-1-f-bandb.test.cpp
• verify/verify-aoj-dpl/aoj-dpl-1-h-bandb.test.cpp

Code

#pragma once

template <typename V, typename W, typename D = long double>
struct BranchAndBound {
  vector<pair<V, W>> c;
  V best;

  BranchAndBound(const vector<V>& v, const vector<W>& w) {
    assert(v.size() == w.size());
    vector<int> ord(v.size());
    iota(begin(ord), end(ord), 0);
    sort(begin(ord), end(ord),
         [&](int i, int j) { return D(v[i]) * w[j] > D(v[j]) * w[i]; });
    for (auto& i : ord) c.emplace_back(v[i], w[i]);
  }

  pair<D, bool> relax(int i, V v, W w) {
    D ret = v;
    bool f = true;
    while (i < (int)c.size()) {
      if (w == 0) break;
      if (w >= c[i].second) {
        w -= c[i].second, ret += c[i].first, ++i;
        continue;
      }
      f = false, ret += (D(c[i].first) * w) / c[i].second;
      break;
    }
    return make_pair(ret, f);
  }

  void dfs(int i, V v, W w) {
    if (i == (int)c.size()) {
      best = max(v, best);
      return;
    }
    auto [rel, flg] = relax(i, v, w);
    if (flg) {
      best = max(best, V(rel));
      return;
    }
    if (V(rel) < best) return;
    if (w >= c[i].second) dfs(i + 1, v + c[i].first, w - c[i].second);
    dfs(i + 1, v, w);
    return;
  }

  V run(W w) {
    dfs(0, best = 0, w);
    return best;
  }
};

/**
 * @brief 0-1ナップサック問題の分枝限定法による解法
 * @docs docs/dp/branch-and-bound.md
 */

#line 2 "dp/branch-and-bound.hpp"

template <typename V, typename W, typename D = long double>
struct BranchAndBound {
  vector<pair<V, W>> c;
  V best;

  BranchAndBound(const vector<V>& v, const vector<W>& w) {
    assert(v.size() == w.size());
    vector<int> ord(v.size());
    iota(begin(ord), end(ord), 0);
    sort(begin(ord), end(ord),
         [&](int i, int j) { return D(v[i]) * w[j] > D(v[j]) * w[i]; });
    for (auto& i : ord) c.emplace_back(v[i], w[i]);
  }

  pair<D, bool> relax(int i, V v, W w) {
    D ret = v;
    bool f = true;
    while (i < (int)c.size()) {
      if (w == 0) break;
      if (w >= c[i].second) {
        w -= c[i].second, ret += c[i].first, ++i;
        continue;
      }
      f = false, ret += (D(c[i].first) * w) / c[i].second;
      break;
    }
    return make_pair(ret, f);
  }

  void dfs(int i, V v, W w) {
    if (i == (int)c.size()) {
      best = max(v, best);
      return;
    }
    auto [rel, flg] = relax(i, v, w);
    if (flg) {
      best = max(best, V(rel));
      return;
    }
    if (V(rel) < best) return;
    if (w >= c[i].second) dfs(i + 1, v + c[i].first, w - c[i].second);
    dfs(i + 1, v, w);
    return;
  }

  V run(W w) {
    dfs(0, best = 0, w);
    return best;
  }
};

/**
 * @brief 0-1ナップサック問題の分枝限定法による解法
 * @docs docs/dp/branch-and-bound.md
 */

Back to top page