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;
}
  • 題目連結：P202 小明要去便利商店買東西，裡面有很多商品，每個商品都有自己的價錢和小明的喜歡值，今天告訴你小明總共有多少錢，請在每個產品最多可以買一個的情況下，請輸出小明買的所有東西喜歡值的最大總和值

位元枚舉的應用

  • 通過位元枚舉，可以生成一組元素的所有可能子集，從而進行子集計算和操作。
  • 位元枚舉也可以用於生成一組元素的所有可能排列。
  • 在某些問題中，可以使用位元枚舉來表示狀態空間中的所有可能狀態，從而實現狀態壓縮和增加程式效率。
Back to top