bit全探索(python)

bit全探索の考え方からソースコードまで

bit全探索は二択の選択の中の選択肢を全部列挙する為のアルゴリズムである。
例
みかん、りんご、ぶどうの3個の中から買い物する可能性の組み合わせは何通り有るか。
買う、買わないの二択が何通り有るかの組み合わせを求める問題である。

考え方

①何通りあるかを考える。

2択が3種類あるので2の3乗で8通りある。

print(2**3)
print(1<<3) #1を2進数で考えて左に３シフトさせると３乗した事と同じになる

#8
#8

②組み合わせを二進数で考える。

0は二進数で000なので何も買わない。
1は二進数で001なので3個目のぶどうの位置のフラグが立っているのでぶどうだけ買う。
2は二進数で010なので2個目のりんごの位置のフラグが立っているのでぶどうだけ買う。
3は二進数で011なので2個目のりんごの位置のフラグと3個目のぶどうの位置のフラグが立っているのでりんごとぶどうを買う。

以下同文

③3個選択肢があるので3回ループを回し、何bit目が1になっているか(フラグがたつ)を確認する。

ibitの位置のフラグを確認する為のコードはif (i>>j)&1:でわかる。

例１：

i=1(001)
j=0

1を右に0回シフトさせると1番右にある数字は何か。またそれが１ならtureを返すという意味である。

例2：

i=2(010)
j=1

2を右に1回シフトさせると1番右にある数字は何か。またそれが１ならtureを返すという意味である。

for i in range(3):
    for j in range(3):
        if (i>>j)&1: #ここで何bit目のフラグが立っているかを確認する。
            print(str('i')+'の時は'+str('j')+'番目のフラグが立っているよ!')



# 1の時は0番目のフラグが立っているよ!
# 2の時は1番目のフラグが立っているよ!
# 3の時は0番目のフラグが立っているよ!
# 3の時は1番目のフラグが立っているよ!
# 4の時は2番目のフラグが立っているよ!
# 5の時は0番目のフラグが立っているよ!
# 5の時は2番目のフラグが立っているよ!
# 6の時は1番目のフラグが立っているよ!
# 6の時は2番目のフラグが立っているよ!
# 7の時は0番目のフラグが立っているよ!
# 7の時は1番目のフラグが立っているよ!
# 7の時は2番目のフラグが立っているよ!

④フラグが立っている時処理の中でみかん、りんご、ぶどうをそれぞれ出力すれば終わり。

atcoderでの実際の例題の答え(python)

167回ABCテスト-C問題
https://atcoder.jp/contests/abc167/tasks/abc167_c

import numpy as np

n,m,x = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
c = [a[i].pop(0) for i in range(n)]
ans = []
for s in range(1<<n):
    cost = 0
    mi = np.array([0]*m)
    for i in range(n):
        if (s>>i)&1:
            cost += c[i]
            mi += np.array(a[i])

    if np.all(mi >= x):
        ans.append(cost)
if ans:
    print(min(ans))
else:
    print('-1')