位元枚舉

簡介

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

例如，對於集合 $\{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);
    }
}