meet in the middle

半分全列挙について

タグ brute force meet in the middle

  • 組み合わせの表現が爆発するとき、その表現を半分に分割して探索する
  • Xの値を得たい時、プロセスAでwを作り、プロセスBでX-wを作るとこの結果の組み合わせが特定のパターンの探索になっている

具体的な例

N個の重さw_iの品物を組合わせてXの重さを作る時、何通りあるか

もとの問題

入力

N X
w_1
w_2
.
.
.
w_n

5 5
1
1
2
3
4

コード

from collections import defaultdict

N, X = list(map(int, input().split()))

A = []
B = []

for i in range(N):
    w = int(input())
    if i % 2 == 0:
        A.append(w)
    else:
        B.append(w)


def has_bit(n, i):
    return (n & 1 << i) > 0


dic = defaultdict(int)

for n in range(1 << len(B)):
    w = 0
    for i in range(N):
        if has_bit(n, i):
            w += B[i]
    dic[w] += 1


ans = 0
for n in range(1 << len(A)):
    w = 0
    for i in range(N):
        if has_bit(n, i):
            w += A[i]
    ans += dic[X - w]

print(ans)