スポンサーリンク

bit全探索で動的計画法を実装する JavaScript

スポンサーリンク
bit全探索で動的計画法を実装する JavaScript アルゴリズム
スポンサーリンク

スポンサーリンク

概要

AtCoderとかをやっていると、
動的計画法(DP)、部分和といった問題とかに遭遇したりしますが、1から実装しようとすると面倒だったりします。
(というよりも、再帰処理で書くのが苦手だったりするからです…)
こんな時に、ビット演算を用いてパターンをひとまず網羅してから実装することがあります。
ここではJSを例に紹介します。

サンプル1

シフト演算で実装する
コード

function main(n) {
    for (let bit = 0; bit < (1 << n); bit++) {
        let row = []
        for (let i = 0; i < n; i++) {
            if (bit & (1 << i)) {
                row.push(i)
            }
        }
        console.log(row)
    }
}
main(4);

このコードの結果は次のようになります。
結果

0
1
0,1
2
0,2
1,2
0,1,2
3
0,3
1,3
0,1,3
2,3
0,2,3
1,2,3
0,1,2,3

部分和の問題を解いてみます。

// [問題]
// 問: [3, 7, 8, 12, 13, 18] の部分和が 27 になる部分集合を求めよ。
// 答: 存在する。[7, 8, 12]

function fetchBitPattern(n, f) {
    for (let bit = 0; bit < (1 << n); bit++) {
        let row = []
        for (let i = 0; i < n; i++) {
            if (bit & (1 << i)) {
                row.push(i)
            }
        }
        f(row)
    }
}

function main() {
    const Q = [3, 7, 8, 12, 13, 18]
    const A = 27
    fetchBitPattern(Q.length, (bit) => {
        let s = 0
        let tmp = []
        for (let i = 0; i < bit.length; i++) {
            s += Q[bit[i]]
            tmp.push(Q[bit[i]])
        }
        if (s === A) {
            console.log(tmp)
        }
    })
}

main()
[7,8,12]

と表示されます。

サンプル2

toStringメソッドで実装する。

function main(n) {
    for (let i = 0; i < Math.pow(2, n); i++) {
        let row = []
        let t = i.toString(2)
        for (let j = t.length; j < n; j++) {
            t = '0' + t
        }
        t = t.split('').map(Number)
        for (let j = 0; j < t.length; j++) {
            if (t[j] === 1) {
                row.push(j)
            }
        }
        console.log(row)
    }
}
main(4)

このコードの結果は次のようになります。

3
2
2,3
1
1,3
1,2
1,2,3
0
0,3
0,2
0,2,3
0,1
0,1,3
0,1,2
0,1,2,3

同じく部分和問題を解いてみます。

// [問題]
// 問: [3, 7, 8, 12, 13, 18] の部分和が 27 になる部分集合を求めよ。
// 答: 存在する。[7, 8, 12]

function fetchBitPattern(n, f) {
    for (let i = 0; i < Math.pow(2, n); i++) {
        let row = []
        let t = i.toString(2)
        for (let j = t.length; j < n; j++) {
            t = '0' + t
        }
        t = t.split('').map(Number)
        for (let j = 0; j < t.length; j++) {
            if (t[j] === 1) {
                row.push(j)
            }
        }
        f(row)
    }
}

function main() {
    const Q = [3, 7, 8, 12, 13, 18]
    const A = 27
    fetchBitPattern(Q.length, (bit) => {
        let s = 0
        let tmp = []
        for (let i = 0; i < bit.length; i++) {
            s += Q[bit[i]]
            tmp.push(Q[bit[i]])
        }
        if (s === A) {
            console.log(tmp)
        }
    })
}

main();
[7,8,12]

と表示されます。

見ての通り、どちらのサンプルもをゴリゴリとループで片付けているので必ずしも効率的ではないと思います。

参考

ビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜 - Qiita
# はじめに はじめまして。 (でリサーチャーをしている大槻 (通称、けんちょん) です。 C や C++ を使用しているとしばしば**ビット**演算を行う場面...
ビットDPの思考回路について
以下のコードのアルゴリズムの思考回路がよくわかりません。 ビットDPを使っているらしいのですが、どういう風にビット演算子を使うとDPになるのか原理が分かりません(なぜDPが成立するのかがわからない)。 また、どのようにすればこのような思考でコードをかけるのでしょうか? どなたか分かる方はいらっしゃるでしょうか? コ...
タイトルとURLをコピーしました