Zenn
🚀

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

2022/04/26に公開
C++
#
競技プログラミング
AtCoder
アルゴリズム
tech

はじめに

最近ようやく重い腰を上げ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進数表記を用いて探索をしていきます。

部分集合 2進数表記 10進数表記
\{\} 000 0
\{A_0\} 001 1
\{A_1\} 010 2
\{A_0,A_1\} 011 3
\{A_2\} 100 4
\{A_0,A_2\} 101 5
\{A_1,A_2\} 110 6
\{A_0,A_1,A_2\} 111 7

ここから実際にコードに落とし込んでいきます。
まずは、上の表を列挙するため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記事にある問題を扱います。
https://qiita.com/u2dayo/items/68e35815659b1041c3c2

N 個の商品があります。i番目の商品の値段はA_i円で、買ったときに得られる満足度はB_iです。あなたはそれぞれの商品を『買う』か『買わないか』、自由に決めることができます。（一つの商品を 2 個以上買うことはできません）
あなたはW円持っていて、はじめの満足度は0です。合計金額がW円以下になるように商品を買って、得られる満足度の最大値を求めてください。

例1に比べて少し複雑になりましたが、やることは同じです。

回答

#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;
}

値段を扱う配列Aと満足度を扱う配列Bを用意して、bitのi番目が1の時にsumにA[i]、satにB[i]を加算しています。

bit全探索の注意点

コードでも記述しているようにbit全探索では2^Nのループが発生します。2^Nは部分集合の個数で指数関数的に増加していくため、Nが大きくなると探索に時間がかかりすぎてタイムアウトになってしまいます。

おわりに

bit全探索も単なる全探索で、部分集合の個数を列挙して処理していることがわかりました。実際にアルゴリズムを言語化して文字に起こしてみると、処理のイメージが湧いていいアウトプットになりました。

AtCoder頑張ります🙌

Discussion