ビット全探索について

今日は学んだについてメモしていこうと思います。
先日書いた記事ではなにかゲームを作ろうとしていましたが、
今日はビット全探索について学んだことを自分なりにまとめて
見ようと思います。あまり難しい事は言わないようにします。
てゆうか自分があまりわからない。

ビット全探索とは

まずビット全探索とは何かについて簡単に説明します。
名前の通り２進数を使って０が「使わない」１が「使う」として、
部分集合を列挙して探索するものである。

例題を見ていきましょう

ALDS_5_A - 総当たり　

JavaScriptでの答え。

js.js

    let N = Number(lines[0]);
    let S = lines[1].split(" ").map(Number);
    let p = Number(lines[2]);
    let m = lines[3].split(" ").map(Number);
    let arr = [];
    for(let i = 0; i < (1 << N);i++) {
        let sum = 0;
        for(let j = 0; j < N; j++) {
          if(i & (1 << j)) {
            sum += S[j];
          }
        }
       arr.push(sum);
    }
    for(let i = 0; i < p;i++) {
        let fire = false;
        for(let j = 0;j < arr.length;j++) {
            if(arr[j] === m[i]) {
                fire = true;
            }
        }
        if(fire) {
            console.log("yes")
        }else {
            console.log("no")
        }
    }

自分で言うのはなんですがあまり良いコードではないですけど許してください。

まず上から６行目くらいのforの行が気になると思います。まずここから見ていきましょう。

js.js

for(let i = 0; i < (1 << N);i++) {
}

(1 << N)この部分を簡単に言うと2^Nをしています。Nが3だとすると8になるということです。

js.js

if(i & (1 << j)) {
  sum += S[j];
}

次にこの行について見ていきましょう。
この行が何をしてるかというと上の説明で行った2^Nまでの整数を２進数に直し
1かどうか判定しています。
例えばNが３のときは
000
001
010
011
100
101
110
111
このように１から８までの整数を２進数表記で1かどうか判定しています。
この内一つの２進数表記「001」を例にすると
「０」使わない
「０」使わない
「１」使わない
ということになります。

まとめ

ビット全探索は(1 << N)でN^2して、(i & (1 << j))１かどうか判定するものです。
とても便利なものですが処理数が指数関数として増えていくため制約を見てできるかどうか
見積もってから実装しましょう。