すずめでも分かる「bit全探索」

記憶喪失になってbit全探索を１から理解しないといけなくなったときのために、(自分用に)解説しておこうと思います。

bit全探索とは

部分集合を列挙するときに使えるアルゴリズムです。

つまり、こういうことができます。

実装はこんな感じ

for (int bit = 0; bit < (1 << n); ++bit) {
  for (int i = 0; i < n; ++i) {
    if (bit & (1 << i)) {
      //何か処理を書く
    }
  }
}

これを見せられても、何をしているのか訳がわかりませんね。細かく見てみましょう。

for (int bit = 0; bit < (1 << n); ++bit) って何してるの？

ここで特にわからないのは、<<の部分だと思います。<<はシフト演算子と呼ばれています。シフト演算子は、数値の各ビットを左または右へシフトさせるための演算子です。<<だと左に、>>だと右にいきます。

各ビットをシフトするということは、下図のように遷移していくことを表します。

2進数の状態で遷移します！(10進数で35が350になったりしません！！！)

すずめ「1が1回左にシフトされるとどうなりますか？」

うさぎ「00001が00010になるので、10進数だと2になります。」

すずめ「では、2が1回左にシフトされるとどうなりますか？」

うさぎ「00010が00100になるので、4になります！」

ここまでで、シフトされる度に2倍になっていっているということが分かると思います。

ということは、for (int bit = 0; bit < (1 << n); ++bit) {の1<<nは、「1をn回左にシフトする」=「2のn乗」ですね！

if (bit & (1 << i)) の部分

ここでは何をしているのでしょうか。

&は、各ビットについて「両方のビットが1ならば1」という操作を適用する演算子です。for文によってn回シフトされるので、下図のように全ての桁のbitがたっているかどうかを調べることができます！

このビットを、その数値を取るか取らないかの2つの状態に当てはめることによって、全探索が行えます！具体的に言うと、C - Skill Upの問題で2冊の参考書が売っていたとするとき、「両方買わない」「１冊目を買う」「２冊目を買う」「１冊目と２冊目を買う」を、「00」「01」「10」「11」に当てはめて調べることができます。(ほら、全部で2のn乗の状態がありますね！)

実装しよう

C - Skill Upを解きます。

bit全探索を理解できると、やるだけですね！！

実装(クリックしてください)

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n, m, x;
  cin >> n >> m >> x;
  int INF = 1010101010;
  int res = INF;

  vector<int> c(n);
  vector<vector<int>> a(n, vector<int>(m));

  for (int i = 0; i < n; i++) {
    cin >> c[i];
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }

  for (int bit = 0; bit < (1 << n); ++bit) {
    int total = 0;
    vector<int> p(m);
    for (int i = 0; i < n; ++i) {
      if (bit & (1 << i)) {
        for (int j = 0; j < m; j++) {
          p[j] += a[i][j];
        }
        total += c[i];
      }
    }
    bool ok = true;
    for (int i = 0; i < m; i++) {
      if (p[i] < x) ok = false;
    }
    if (ok) res = min(res, total);
  }
  if (res == INF)
    cout << -1 << endl;
  else
    cout << res << endl;
}

おしまい。