はじめに
bit全探索は、bit演算を使った全探索アルゴリズムの一種です。 部分和問題に応用できます。 例としては、下記のような問題です。
【例題】 N枚のカードがあり、カードA1 ～ANにそれぞれ異なる値段がつけられています。購入するカードをいくつか選んだ場合、購入金額がS円となる組み合わせは存在しますか？
bit全探索を用いた解法です。
#include <iostream> #include <vector> using namespace std; int main(){ int N = 0; int S = 0; cin >> N; cin >> S; vector<int> A(N, 0); for (int i = 0; i < N; i++) cin >> A[i]; int sum = 0; bool answer = false; for (int pattern = 0; pattern < (1 << N); pattern++) { sum = 0; for (int bit = 0; bit < N; bit++) { if (pattern & (1 << bit)) { sum += A[bit]; } } if (sum == S) { answer = true; break; } } if (answer == true) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
bit全探索のアルゴリズム
2進数表記による各組み合わせの導出
bit全探索のアルゴリズムでは2進数を用います。
桁数をデータ数とするため、データ数をNとすると組み合わせの総数は2Nとなります。
N=3の場合は、8つの組み合わせを0～7と表します。
さらに、0～7を2進数表記することで、1となっている桁を選択したデータと考えることができます。
カードAの値段それぞれをA1=30円,A2=40円,A3=20円とし、購入金額Sが50円となる組み合わせを見つける場合、購入金額がSとなる組み合わせが見つかるまで0から一つずつ確認していくことになります。この場合は6つ目の組み合わせで見つかりました。
bit全探索の実装
bit全探索を実装していきます。例題を再度提示します。
【例題】 N枚のカードがあり、カードA1 ～ANにそれぞれ異なる値段がつけられています。購入するカードをいくつか選んだ場合、購入金額がS円となる組み合わせは存在しますか？
まずは、カードの枚数N、購入金額S、カードのそれぞれの値段A1 ～ANを入力していきます。
int N = 0;
int S = 0;
cin >> N;
cin >> S;
vector<int> A(N, 0);
for (int i = 0; i < N; i++)
cin >> A[i];
入力後、bit全探索の処理に入っていきます。全探索の基本的な処理は下記のとおりです。
int sum = 0;
bool answer = false;
for (int pattern = 0; pattern < (1 << N); pattern++) {
sum = 0;
for (int bit = 0; bit < N; bit++) {
if (pattern & (1 << bit)) {
sum += A[bit];
}
}
if (sum == S) {
answer = true;
break;
}
}
各組み合わせごとの購入金額をsum, 判定結果をanswerとして初期化します。
int sum = 0;
bool answer = false;
bit全探索では、選択肢の数に基づいて総組み合わせ数を算出する必要がありますが、シフト演算子<<を使用することで簡単に算出することができます。<<は左シフトで、2進数であらわされたデータを指定した分、左にシフトします。
カードAが3枚の場合は、3桁の2進数で表すことができる数値は0～7、つまり総組み合わせ数は8であり、1 << 3に一致します。 よって、N枚のカードから購入するカードを選択する場合、総組み合わせ数は 1 << Nで表すことができます。 forを使うことで、N枚のカードから選択する場合の組み合わせを一つずつ確認できます。patternが各組み合わせを示す数値となります。
for (int pattern = 0; pattern < (1 << N); pattern++) {
//各組み合わせを確認
}
各組み合わせの購入金額を算出します。 まず、組み合わせを示す数値patternに対して、2進数で表記した場合に「1」となっている桁を探します。「1」となっている桁が見つかった場合、その桁に対応するデータを持ってきて加算処理を行っています。 この処理によって、sumに各組み合わせの購入金額が算出されます。
sum = 0;
for (int bit = 0; bit < N; bit++) {
if (pattern & (1 << bit)) {
sum += A[bit];
}
}
算出された購入金額がSと一致した場合、判定結果をtrueとし、ループ分を抜けます。
if (sum == S) {
answer = true;
break;
}
最後に判定結果を出力します。
if (answer == true)
cout << "Yes" << endl;
else
cout << "No" << endl;
全体のコードは以下です。
#include <iostream> #include <vector> using namespace std; int main(){ int N = 0; int S = 0; cin >> N; cin >> S; vector<int> A(N, 0); for (int i = 0; i < N; i++) cin >> A[i]; int sum = 0; bool answer = false; for (int pattern = 0; pattern < (1 << N); pattern++) { sum = 0; for (int bit = 0; bit < N; bit++) { if (pattern & (1 << bit)) { sum += A[bit]; } } if (sum == S) { answer = true; break; } } if (answer == true) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
まとめ
bit全探索により、N個のものに対して「選ぶ」「選ばない」、「買う」「買わない」といった選択をした場合の探索を行うことができます。(部分和問題)
N個から選択する場合の総組み合わせ数は2N通りあります。
N個から選択する場合の組み合わせを2進数のN桁の値で表すことで、「選ぶ」「選ばない」を「１」「０」と考えることができます。
