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

    小明要去便利商店買東西，裡面有很多商品，每個商品都有自己的價錢和小明的喜歡值，今天告訴你小明總共有多少錢，請在每個產品最多可以買一個的情況下，請輸出小明買的所有東西喜歡值的最大總和值

  • 題目連結：P203

位元枚舉的應用

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

遞迴枚舉

遞迴枚舉可以說是在使用爆搜(Brute Force)最常用到的一種方法，可以藉由遞迴來找出所有狀態和所有結果，和位元枚舉有相似之處，以下直接使用上面用到的例題Ex203

然而，遞迴最重要的是建立遞迴關係式，但通常在使用遞迴枚舉時可以很容易想出來，以這題來說，其中一項要不是選就是不選，用這種方法就可以寫出類似以下程式碼

int v[50];
long long total = 0;
int n; // 總共有幾項
void f(long long now, long long i) { // now代表目前的的總樹，i表示枚舉到第幾項
    if(i == n) {
        // 枚舉完其中一種狀態
        return;
    }
    f(now + v[i], i + 1); // 選
    f(now, i + 1); // 不選
}

最後再根據這題的描述，我們可以枚舉其中一個籃子的總數，就可以完成這題了

程式碼：

#include <iostream>
#define ll long long
using namespace std;
int v[50];
long long ans = 1e15;
long long total = 0;
int n;
void f(long long now, long long i) {
    if(i == n) {
        ans = min(abs(total - now - now), ans);
        return;
    }
    f(now + v[i], i + 1);
    f(now, i + 1);
}
int main()
{

    cin >> n;
    total = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> v[i];
        total += v[i];
    }
    f(0, 0);
    cout << ans << '\n';
    return 0;
}

遞迴枚舉練習題

將P202、P203轉換成遞迴枚舉版本

Back to top