LoginSignup
49
20

More than 1 year has passed since last update.

こわくないbit全探索2 基本編1: 簡単な例題でbit全探索をやってみよう!【競プロ解説】

Last updated at Posted at 2021-11-15

競技プログラミング(AtCoder)初心者が、最初に突き当たる壁になることが多いアルゴリズムのひとつに『bit全探索』があります。

この記事では、その『bit全探索』についてできる限り丁寧に解説をしていきます。

※この記事ではPythonを使った実装を解説していますが、他の言語を使っている方も読むと理解の助けになるはずです。C++でも使える実装は基本編2で解説しています。

記事リンク

1. 入門編 bit全探索ってなに? : bit全探索はどんなことをするアルゴリズムなのか解説します。 
2. 基本編1 簡単な例題でbit全探索をやってみよう! : 簡単な例題(部分和問題)で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう! : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう! : AtCoderのbit全探索を使う問題のヒントとコード(Python・C++)を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう! : 再帰関数を使ってbit全探索に似た問題を解きます。

質問先など

ご指摘・ご質問はツイッター・マシュマロ・Discordサーバーまでお気軽にどうぞ!

Twitter: u2dayo
マシュマロ: https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー(質問や記事の感想・リクエストなどどうぞ!) : https://discord.gg/jZ8pkPRRMT

よかったらLGTM拡散していただけると喜びます!

bit全探索をやってみよう!

『部分和問題』

$N$ 個の正の整数 $A_1,A_2,\dots,A_N$ が与えられます。
この中からいくつかの整数を選んで、選んだ数を足し合わせた合計が $W$ になる選び方が何通りあるか出力してください。

制約
$1\le{N}\le{16}$
$1\le{A_i}\le{100}$
$1\le{W}\le{10000}$

入力

入力は以下の形式で標準入力から与えられます。

$N\ \ W$
$A_1\ \ A_2\ \ \dots\ \ A_N$

出力

1行で条件を満たす選び方の数を出力してください。

これは部分和問題という有名な問題です。

$N=5,\ A=\{1,2,3,6,8\},\ W=10$ の場合を考えてみます。

$\{2,8\}$ を選ぶと、$2+8=10$ にすることができます。$\{1,2,3\}$ を選んでも $1+2+3=6$ ですからダメです。

今例にあげた選び方・何も選ばない場合を含めて、全部で $2^5=32$ 通りの選び方があります。すべてのありえる選び方を列挙したのが下の図です。(○は使う場合、×は使わない場合をあらわします)。
image.png

部分和問題のbit全探索を使った解き方

この問題を解くためには、先ほどの図のように『すべての選び方について選んだ数字を足し合わせた合計を求めて、$W$ ちょうどになる選び方がいくつあるか数える』コードを書けばいいです。つまり

  • 『選ぶ』『選ばない』の組み合わせ方、$2^N$ 通りすべてをもれなく列挙する
  • それぞれの組み合わせについて、選んだ整数の合計を求めて、$W$ と等しいなら答えに $+1$ する

というコードを実装すればいいです。

実装編

bit全探索で部分和問題を解くコードの方針が立ったので、この問題を解くコードを書いていきましょう。

選び方がわかれば、合計を求めて判定するのは簡単

数字の選び方 $1$ パターンに対して、選んだ数字の合計が $W$ かどうかの判定は簡単にできます。例えば $A_1,A_3,A_5$ を使うと決まっているときは、 $A_1 +A_3+A_5$ を計算して、$W$ と等しいか判定するだけです。

全列挙がむずかしい

難しいのは、選び方の組み合わせを全列挙する方法です。慣れてしまえば毎回同じパターンを書くだけなのですが、慣れるまでが少し大変ですし、タイピング量も多くなりがちです。

普通は大変なのですが、Pythonを使っている方は、標準ライブラリをうまく使うことで、全列挙を簡単に実装することができます。(C++の人は次の章まで待ってね)

Python のbit全探索はitertoolsモジュールのproduct関数を使うと楽!

Pythonでは、itertools モジュールの product 関数を使うと簡単にbit全探索を実装できます。(公式ドキュメントのリンク

from itertools import product

for pro in product((0, 1), repeat=N):
    # proは長さN、各要素が整数 0 か 1 のタプル

このように書くことで、『長さ $N$ 、各要素が 10 のタプル』としてありえるものを、重複なく $2^N$ 個 全て列挙することができます。

『長さ $N$ 、各要素が 10 のタプル』とは、たとえば $N=5$ なら (1, 0, 1, 1, 1) などが該当します。そして、このタプルの $i$ 番目の要素が1なら $A_i$ を『選ぶ』、0なら『選ばない』とみなします。

(1, 0, 1, 1, 1)なら、$A_1,A_3,A_4,A_5$ を選んで、 $A_2$ は選ばない、ということです。(先ほどの図の○が1に、×が0に対応しています)

productで生成されるタプルを全部見てみる

repeat=5を指定した次のコードを実行して、生成されるタプルをすべて見てみましょう。

from itertools import product

for pro in product((0, 1), repeat=5):
    print(pro)

$2^5=32$ 通りの『長さ $5$ 、各要素が 10 のタプル』がすべて表示されるはずです。実行してみると、以下の出力を得られます。

(0, 0, 0, 0, 0)
(0, 0, 0, 0, 1)
(0, 0, 0, 1, 0)
(0, 0, 0, 1, 1)
(0, 0, 1, 0, 0)
(0, 0, 1, 0, 1)
(0, 0, 1, 1, 0)
(0, 0, 1, 1, 1)
(0, 1, 0, 0, 0)
(0, 1, 0, 0, 1)
(0, 1, 0, 1, 0)
(0, 1, 0, 1, 1)
(0, 1, 1, 0, 0)
(0, 1, 1, 0, 1)
(0, 1, 1, 1, 0)
(0, 1, 1, 1, 1)
(1, 0, 0, 0, 0)
(1, 0, 0, 0, 1)
(1, 0, 0, 1, 0)
(1, 0, 0, 1, 1)
(1, 0, 1, 0, 0)
(1, 0, 1, 0, 1)
(1, 0, 1, 1, 0)
(1, 0, 1, 1, 1)
(1, 1, 0, 0, 0)
(1, 1, 0, 0, 1)
(1, 1, 0, 1, 0)
(1, 1, 0, 1, 1)
(1, 1, 1, 0, 0)
(1, 1, 1, 0, 1)
(1, 1, 1, 1, 0)
(1, 1, 1, 1, 1)

確かに $2^5=32$ 通りすべての『長さ $5$ 、各要素が 10 のタプル』を全て列挙できています。(先ほどの画像の○と×に対応しています)

このタプルを判定関数に渡して、選んだ数字の合計が $W$ と等しいか判定するだけです。

コード

慣れている人が見ると、やや冗長な部分に見える部分もあるかもしれませんが、今回はわかりやすさを重視しています。

入力受け取りとインポート

いつもどおり $N,W$ を整数として受け取り、また $N$ 個の整数 $A_i$ をリストで受け取ります。

また、itertoolsモジュールのproduct関数を使うために、from itertools import product と書きます。

from itertools import product

N, W = map(int, input().split())
A = list(map(int, input().split()))

bit全探索の組み合わせを全列挙する部分

product((0, 1), repeat=N)をforループで回して、長さ $N$ の 01 からなるタプルを、判定関数に $1$ つずつ渡していきます。

ans = 0
for pro in product((0, 1), repeat=N):
    ans += judge(pro)  #  タプルproを渡す judgeは選び方の合計がWなら1, そうでないなら0を返す 

print(ans)

判定部分

渡されたタプルをforループで見ていって、$i$ 番目が1ならA[i] を使うので合計に足します。

合計が $W$ ならば $1$ を返して、そうでなければ $0$ を返します。

def judge(pro):
    S = 0
    for i in range(N):
        if pro[i]:  # pro[i] が 1 なら A[i] を足す(if文の判定では、0はFalse扱い、他の整数はTrue扱いされます)
            S += A[i]

    if S == W:  # S == W なら +1、そうでなければ 0 を返す
        return 1
    else:
        return 0

全体

from itertools import product  # import文は一番上にまとめておくほうが良いです


def judge(pro):
    S = 0
    for i in range(N):
        if pro[i]:  # pro[i] が 1 なら A[i] を足す(if文の判定では、0はFalse扱い、他の整数はTrue扱いされます)
            S += A[i]

    if S == W:  # S == W なら +1、そうでなければ 0 を返す
        return 1
    else:
        return 0


N, W = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
for pro in product((0, 1), repeat=N):
    ans += judge(pro)  #  タプルproを渡す judgeは選び方の合計がWなら1, そうでないなら0を返す 

print(ans)

実行してみる

サンプル1
入力
5 10
1 2 3 6 8
出力
2
サンプル2
入力
8 1
1 1 1 1 1 1 1 1
出力
8
サンプル3
入力
1 100
100
出力
1
サンプル4
入力
16 34
5 4 8 7 1 6 8 5 9 7 6 7 8 9 4 4
出力
1057
サンプル5
入力
16 234
33 65 52 40 95 30 71 95 45 14 18 48 88 16 76 39
出力
77

おまけ:部分和問題は『動的計画法』でも解ける

完全におまけの話をします。bit全探索よりも難しいアルゴリズムの話なので、今理解する必要はありません。

部分和問題は動的計画法(Dynamic Programming, DP)というアルゴリズムを使って $O(NW)$ の計算量で解くこともできます。$W$ が比較的小さい場合は、 $N$ が大きい場合でも高速に解くことができます。

ただし、例えば $W\le10^{18}$ , $N\le16$ のように$W$ が非常に大きく、$N$ が小さい場合はbit全探索でないと解けません。制約によってアルゴリズムを使い分けるのも重要です。

動的計画法のコード

N, W = map(int, input().split())
A = list(map(int, input().split()))

dp = [[0] * (W + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i, x in enumerate(A):
    for j in range(W + 1):
        dp[i + 1][j] += dp[i][j]
        if j - x >= 0:
            dp[i + 1][j] += dp[i][j - x]

print(dp[N][W])

記事リンク(再掲)

1. 入門編 bit全探索ってなに? : bit全探索はどんなことをするアルゴリズムなのか解説します。 
2. 基本編1 簡単な例題でbit全探索をやってみよう! : 簡単な例題(部分和問題)で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう! : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう! : AtCoderのbit全探索を使う問題のヒントとコード(Python・C++)を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう! : 再帰関数を使ってbit全探索に似た問題を解きます。

49
20
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
49
20