【アルゴリズム学習#1】bit全探索

はじめに

最近ようやく重い腰を上げAtCoderに参加し始めました。まだ2回した参加していないので灰色コーダーです。まずは目指せ茶！ということで学習したアルゴリズムをアウトプットしていきます。

bit全探索とは

bit演算を利用した全探索アルゴリズムで、部分集合を全列挙して処理することができます。

（名前がちょっと難しくて勉強するのを躊躇っていたけど、実際やっていることはそこまで複雑じゃない）

bit全探索の例

例1

まずは部分和問題の簡単な例を見ていきます。

N個の正の整数A_0,A_1,...,A_{N-1}と正の整数Bが与えられます。
A_0,A_1,...,A_{N-1}の中からいくつかの整数を選んで総和がBになるかどうか判定してください。総和がBになる場合はYes、ならない場合はNoを出力してください。

N=4, B=10, A=\{1,4,5,2\}の場合は、A_0+A_1+A_2=10となるためYesが出力されます。N=4, B=11, A=\{1,4,5,3\}の場合はどの組み合わせでも11にならないためNoが出力されます。

この問題では、N個の整数の部分集合を全て列挙して要素の総和をBと比較することで解くことができます。N個の整数の部分集合は2^N通り存在します。Nが3の場合は、\{\},\{A_0\},\{A_1\},\{A_2\},\{A_0,A_1\},\{A_1,A_2\},\{A_0,A_2\},\{A_0,A_1,A_2\}の8通りとなります。

これを2進数表記にすると以下のようになり、bit全探索ではこの2進数表記を用いて探索をしていきます。

ここから実際にコードに落とし込んでいきます。
まずは、上の表を列挙するためfor文で2^N繰り返します。

for (int bit=0; bit < (1 << N); bit++) {
	cout << bit << endl;
}
// 出力
0
1
2
3
4
5
6
7

(1 << N)と書くことで0~7の8通り全てが出力されていることがわかりますね。上の表を見ると0~7の整数が2進数と正の整数A_0,A_1,...,A_{N-1}と対応づけられており、これを利用して2進数の桁が1になっているかどうかを判定することで処理ができます。

実際には以下のように判定します。

for (int bit=0; bit < (1 << N); bit++) {
  //=== ここから追加 ===
  for (int i=0; i < N; i++) {
    if (bit & (1 << i)) {
      // A[i]に対する処理
    }
  }
  //=== ここまで追加 ===
}

N = 3でbit = 5（0101）の時の処理をステップごとに見ていきます。

1. i = 0の時に(bit & (1 << 0))が判定される
   • 0101と0001の論理積なので0001でtrue
2. i = 1の時に(bit & (1 << 1))が判定される
   • 0101と0010の論理積なので0でfalse
3. i = 2の時に(bit & (1 << 2))が判定される
   • 0101と0100の論理積なので0100でtrue

上の処理を見て分かる通り、i = 0, i = 2の時にA[i]に対する処理を実行しています。

つまり、bitを2進数表記した時のi番目が1の場合に処理をしているということです。この処理を利用して例題を解いたプログラムがこちらです

回答

#include <bits/stdc++.h>
using namespace std;

int main(void){
    // 入力
    int N, B;
    cin >> N >> B;
    vector<int> A(N);
    for (int i=0; i < N; i++) cin >> A[i];
    
    bool exist = false;
    // 2^Nループ
    for (int bit=0; bit < (1 << N); bit++) {
        int sum = 0;
        for (int i=0; i < N; i++) {
	    // bitのi番目が1の時にA[i]加算
            if (bit & (1 << i)) sum += A[i];
        }
        
        if (sum == B) exist = true;
    }
    
    if (exist) cout << "Yes" << endl;
    else cout << "No" << endl;
}

bitを2進数表記した時のi番目が1の時にsumにA[i]を加算しています。そうすることで、5(0101)の場合にはA0とA2の和がBと比較されることになります。

例2

こちらのQiita記事にある問題を扱います。

#include <bits/stdc++.h>
using namespace std;

int main(void){
    int N, W;
    cin >> N >> W;
    vector<int> A(N), B(N);
    for (int i=0; i < N; i++) cin >> A[i];
    for (int i=0; i < N; i++) cin >> B[i];
    
    int max_sat = 0;
    for (int bit=0; bit < (1 << N); bit++) {
        int sum = 0;
        int sat = 0;
        
        for (int i=0; i < N; i++) {
            if (bit & (1 << i)) {
                sum += A[i];
                sat += B[i];
            }
        }
        
        if (sum <= W && max_sat < sat) max_sat = sat;
    }
    
    cout << max_sat << endl;
}