Skip to main content

2.2 位元枚舉和遞迴枚舉

位元枚舉介紹

位元枚舉是一種通過遍歷所有的二進制數字來列舉所有可能的狀態的方法。通過對二進制數字中的每一位進行遍歷，可生成所有可能的狀態。

位元枚舉的優勢和定義：

  • 用二進位的方式來簡單維護枚舉的技巧，程式碼量小
  • 通常使用在枚舉部分只有要或不要(1/0)兩種可能，符合二進位原理
  • 例如：10011代表在第1、2、5項要選擇3、4則不選擇

如何使用位元枚舉

進行位元枚舉的基本概念是通過遍歷所有的二進制數字來產生所有可能的狀態。可以通過以下步驟來實作位元枚舉：

  1. 定義好總共有幾項需要枚舉，在此設訂為$n$項
  2. 枚舉所有狀態：用一個循環從$0$開始到$2^n-1$
  3. 根據每次枚舉到的數字來檢查當前狀態的值，1或0來完成不同操作 以下是簡單的位元枚舉範例程式碼
void e(int n) { // 有n項
    for(int i = 0; i < (1 << n); i++) { // 枚舉所有狀態
        for(int j = 0; j < n; j++) { // 各項遍歷
            if((i >> j) & 1) ... // 當前為1
            else ...// 當前為0
        }
    }
}

位元枚舉範例題

  • 題目連結：Ex203
  • 題目敘述：有$n (1 ≤ n ≤ 20)$ 個蘋果，每一個蘋果都有一個重量$p(1 ≤ p ≤ 10^9)$，現在有兩個籃子，必須把所有蘋果都放到這兩個籃子裡，你可以選擇每一顆蘋果要放到哪一個籃子裡，詢問最後這兩個籃子重量的最小差。
  • 這題可以觀察給定的資料大小會發現$n$非常小，最多只會有$2^n$種狀態，這樣就有機會可以使用位元枚舉
  • 可以想像成放到第一個籃子當前狀態就是0，第二個籃子狀態就是1
  • 注意測試資料範圍，可能會超過int的上限
  • 程式碼：
#include <iostream>
#define ll long long
using namespace std;
ll v[30];
int main()
{
    int n;
    cin >> n;
    ll ans = 1e15;
    ll cnt = 0;
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        cnt += v[i];
    }
    for(int i = 0; i < (1 << n); i++) {
        ll now = 0;
        for(int j = 0; j < n; j++)
        {
            if((i >> j) & 1)
            {
                now += v[j];
            }
        }
        ans = min(ans, abs(cnt - now - now));
    }
    cout << ans << '\n';
    return 0;
}

https://codeforces.com/problemset/problem/1097/B?locale=en

Back to top