位元枚舉

簡介

#

位元枚舉是一種枚舉的技巧，通常用來枚舉所有的子集合。在這個技巧中，我們將集合中的元素用二進位表示，然後對二進位進行枚舉。

例如，對於集合 \({1, 2, 3}\)，我們可以用 \(3\) 個位元來表示，其中第 \(i\) 個位元為 \(1\) 表示元素 \(i\) 在子集合中，為 \(0\) 表示元素 \(i\) 不在子集合中。這樣，我們就可以用 \(000\), \(001\), \(010\), \(011\), \(100\), \(101\), \(110\), \(111\) 來表示所有的子集合。

實作方式

#

首先我們需要一個 \(mask\) 變數，用來儲存目前的子集合，雖然 \(mask\) 是一個整數，但我們可以將其視為一個二進位數字來操作。

如果要枚舉 \(000\) 到 \(111\)，實際上整數就是 \(0\) 到 \(2^n-1\)，也就是 \(0\) 到 \(7\)。因此，我們可以用以下的迴圈來枚舉所有的子集合。

for (int mask = 0; mask < (1 << n); mask++) {
    
}

接著，我們可以用以下的方法來判斷第 \(i\) 個元素是否在子集合中。

if (mask & (1 << i)) {
    // 第 i 個元素在子集合中
}

整個程式碼如下：

for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) {
            // 第 i 個元素在子集合中
        } else {
            // 第 i 個元素不在子集合中
        }
    }
}

這樣，我們就可以用位元枚舉的方式來枚舉所有的子集合了！

例題

#

給定一個長度為 \(n\) 的數列，從中選出一些數字，使得這些數字的和儘可能接近且不超過 \(k\)，請你輸出最接近且不超過 \(k\) 的和。

根據上面介紹的方法，我們可以用以下的程式碼來解決這個問題。

for (int mask = 0; mask < (1 << n); mask++) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) {
            sum += a[i];
        }
    }
    if (sum <= k) {
        ans = max(ans, sum);
    }
}