アルゴリズム力を鍛えるためにけんちょんさんの本を読んでいて、部分和問題のビット全探索でうまく理解できなかったので自分が理解できるまで調べたという話です。
より詳細な解説を読みたいのであればご本人のブログを読むのが良いかと思います。 drken1215.hatenablog.com
部分和問題でのビット全探索
部分和問題について
「部分和問題 (subset-sum problem)」は、要素が数値の集合 S において、要素の総和が M となる部分集合があるか判定する問題です。
ビット演算について
&(AND)
二つのスイッチを比較してどちらも1なら1、どちらか0なら0を返す
c = a & b
a: 10110101
b: 01000101
c: 00000101
用途
ビットでフラグ管理をしている場合の探索
|(OR)
二つのスイッチを比較してどちらかが1なら1、どちらも0なら0を返す
c = a | b
a: 10110101
b: 01000101
c: 11110101
用途
ビットでフラグ管理をしている場合にフラグを立てる場合
!(NOT)または~
スイッチのON/OFFを全て逆転させる
c = !a
a: 10110101
c: 01001010
XOR
二つのスイッチを比較してどちらか片方だけ1なら1、どちらも1または0なら0を返す
c = a ^ b
a: 10110101
b: 01000101
c: 11110000
用途
二つのスイッチの差分を調べる
>>(右ビットシフト)
スイッチのON/OFFを一つ右にずらす。
空いたビットには0埋めが行われて、溢れたビットは消える。
c = a >> 1
a: 10110101
c: 01011010
用途
ループでビット操作する時
<<(左ビットシフト)
スイッチのON/OFFを一つ左にずらす。
他の操作は右ビットシフトと同様。
c = a << 1
a: 10110101
c: 01101010
用途
右ビットシフトと同様
参考
https://qiita.com/Ingward/items/43acda931c8a62c70d2f
ビット全探索の解説
例題
N個の正の整数a0,a1,...,aN－1と正の整数Wが与えられます．a0,a1,...,aN－1の中から何個かの整数を選んで総和をWとすることができるかどうかを判定してください．
例題解説
N個の整数の集合の2Nある部分集合からどの組み合わせでも良いので総和Wになる組み合わせが存在するかを判定する。
たとえば{1,3,7}という整数の集合の部分集合は{},{1},{3},{7},{1,3},{1,7},{3,7},{1,3,7}の8通りある。（23=8通り）
総和が10の場合、{3,7}が該当する。
実装は以下のようになる。以降でこの実装について解説する。
def main(): n, k, a, is_exist = 3, 10, [1, 3, 7], False for bit in range(2 ** n): sum = 0 for i in range(n): if bit & (1 << i): sum += a[n - 1 - i] if sum == k: is_exist = True print("Yes" if is_exist else "No") if __name__ == '__main__': main()
解法
bit全探索
方針としては
1. N個の数列それぞれにビットを当てはめる
2. bit&(1<<i)でそれぞれの数列に当てはめたビットの論理積をとって足し合わせて総和が一致するかを判定
と解いていきます。
N個の数列それぞれにビットを当てはめる
仮に$N=4$の場合、全ての数列は{0, 1, 2, 3}の4つになります。このそれぞれにビットを当てはめると0は001、1は010、2は100、3は1000と置くことができます。
N個の数列の組み合わせを復元する
では総和Wが5である組み合わせを復元するにはどうするか。 以下のように数列N個全てに対して調べ上げます。
for i in range(n): if bit & (1 << i):
$N=4$,$bit=13$の場合にカウンタ変数$i$とif文の条件式の状態は以下のようになります。
| i | 1<<i | bit&(1<<i) |
|---|---|---|
| 0 | 00000001 | 00001101 & 00000001 = 00000001(True) |
| 1 | 00000010 | 00001101 & 00000010 = 00000000(False) |
| 2 | 00000100 | 00001101 & 00000100 = 00000100(True) |
| 3 | 00001000 | 00001101 & 00001000 = 00001000(True) |
総和Wが5となる組み合わせは{0,2,3}ですが、それぞれに当てはまるカウンタ変数$i$でTrueとなります。
1<<iは1(00000001)をiの分だけ左にシフトさせます。これがN個ある整数のフラグとなっています。
そしてbitとの論理積を取ると、フラグとしてシフトさせた位置のビットがどちらも1になっていれば1、どちらかが0であれば0となります。これで最初に数列の各要素に当てはめた数字を足し合わせると総和が求まり、これを全探索して終了となります。
終わりに
この方法だと計算量は$O(2N^{2})$となりあまり優秀とは言えません。動的計画法を使うと$O(NW)$に抑えられるので次はDPに挑戦です。
