## 定義
所謂的枚舉，就是把可能的結果一一列出來，比如要找 $1\sim100$ 中可以同時整除 $2$ 與 $3$ 的整數
這時候如果用枚舉去做，就是把 $1\sim100$ 的整數都列出來，然後判斷是否能整除
不過這是最簡單的一種枚舉，只要用 for 迴圈就可以實現了，常用的枚舉會比較複雜
在一般情況下，窮舉(Enumeration)和暴搜(暴力搜尋/Brute Force)都是枚舉的策略之一
相較於一般的遞迴(計算只是為了答案)，枚舉是不確定"當前可能"是否能達成目標
## 優缺點
優點是枚舉的概念很直觀，就是把所有可能的解找出，並判斷哪些正確，如果執行正確一定能找到解
缺點是效率差，如果題目給予的資料量過大，基本上是不可使用枚舉解題，因為速度太慢了
## 剪枝
定義為當判斷出當前解不能導向最終的有效解或最優解時，就停止繼續從這條路徑往後找可能
比如在排某天的會議時間時，如果第一場會議排到太晚的時間，會讓剩下的會議來不及舉行
所以枚舉會議的時間時，只要第一場會議的時間大於某個數字，就可以暫停枚舉
其他場會議也可以套用同樣的原理，因為剪枝理論上可以用在任何可能當中
剪枝細分還會分成兩種，可行性剪枝與最優性剪枝，但這個在實作上不是很重要
總之剪枝是優化的一種，本質上就是減少枚舉的數量，來讓最後花費的時間減少
## 集合(Set)
集合在枚舉中的概念通常是指題目從一個集合做選擇，可能選擇第一個元素，可能同時選擇好幾個
總之最後的解通常會是不重複的，而概念上來說，解都是原本集合的子集合，近似數學上的組合
實作的方式有兩種，遞迴跟二進制，遞迴通常使用 DFS 窮舉，兩者的概念是相似的，只是表達不同
## DFS 窮舉
DFS 的概念是當進入到一個新的可能情況 $C$ 時，窮舉 $C$ 之後的所有可能情況 $C_1 \sim C_n$
當 $C_1$ 之後的所有可能都走完，就會回朔到 $C$，然後繼續往 $C_2$ 走
如果我們把 DFS 的概念畫成圖，就會像是下面這張"有向圖"
但同樣的，如果我們直接把全部情況都舉出來，會花費很多時間，所以需要剪枝，之後結合例題實作
## 二進制
用二進制去解決枚舉的問題，就是應用到位元運算的方式，剛好可以用 $1$ 和 $0$ 表達選或不選
透過之前的結論可以知道最後總共有 $2^n$ 種可能，而這些可能剛好會是連續的數字，舉個例子
假設我們要在 $1,2,3$ 中做選擇，那我們只選擇 $1$ 就是二進制中的 $100$，代表選、不選、不選
把所有選擇可能列出會像這樣，$000、001、010、011、100、101、110、111$ 共 $8$ 種
其實應該有人發現了，只需要枚舉 $0~2^n-1$ 的數字就可以找出所有排序
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
int A[5] = {1,2,3,4,5} ;
int n = 5 ;
vector<int> ans(n) ;
for (int i=0;i<(1<<n);i++) { // 枚舉 0 ~ 2^n -1
int len = 0 ;
for (int j=0;j<n;j++)
if ((i >> j) & 1) // 右邊數來第 j 位是 1
ans[len++] = A[j] ;
for (int j=0;j<len;j++)
cout << ans[j] << ' ' ;
if (len) cout << '\n' ;
}
return 0 ;
}
```
這個方法不太能用剪枝，因為這裡是直接通往結果
而遞迴跟樹一樣，當前的結果如果不滿足題目要求，那後方所有可能都可以去除
所以能像是平常修剪樹木的人一樣，一次就把一個分岔後方的所有剪掉
但二進制最多就是一次剪一個葉節點，那效率自然就會比較差
## 例題-ZJ a981. 求和問題
[題目連結](https://zerojudge.tw/ShowProblem?problemid=a981)
題目解析 :
這題問哪幾個數字和剛好為 $M$，所以我們可以列出所有可能，舉個例子
假設數字只有 $1,2,3$，那其中一種可能的總和是 $1+2=3$，這時選了 $1,2$ 但沒選 $3$
所以計算所有可能就是把所有數字選跟不選的可能都考慮進去，簡單來說可以畫成之前那樣的圖
方法就是把所有數字排成一排，用 DFS 去跑過所有數字，每到一個新數字都有兩個選擇，選或不選
這樣最後就可以把所有可能都列出來，也就是圖上最右方那層的節點，這時候再判斷總和大小
不過要注意，這裡的選擇順序要先選數字小的，所以提前將資料排序好才能正確選擇
選擇的問題解決了，剩下就是如何記錄選擇的數字，由於我們剛剛的推論可以得知
最後的可能高達 $2^n$ 個，如果陣列一直複製就會讓空間爆炸
同一個陣列不會產生錯誤的概念，因為 DFS 就是一次走到底，只要在回頭的時候處理陣列就好
```cpp=
void dfs(int idx, int sum, int len, vector<int> &ans) {
if (idx >= n) { // 已經沒有數字可選擇
if (sum == m) { // 總和一樣
for (int i=0;i<len;i++) {
cout << ans[i] << ' ' ;
}
cout << '\n' ;
}
return ;
}
ans[len] = num[idx] ;
dfs(idx+1, sum+num[idx], len+1, ans) ; // 選
dfs(idx+1, sum, len, ans) ; // 不選
return ;
}
```
不過很明顯，這裡的時間複雜度太大了，枚舉+輸出的複雜度就是 $O(n\times 2^n)$
所以要用上前面介紹的剪枝優化，其實也很簡單，如果當前總和已經大於 $M$
那之後不論如何選擇都不可能會是 $M$，所以就直接停止枚舉這個可能後續的所有可能
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int n, m, can = 0 ;
int num[31] ;
void dfs(int idx, int sum, int len, vector<int> &ans) {
if (idx >= n || sum == m) { // 已經沒有選擇/不用選擇
if (sum == m) { // 總和一樣
for (int i=0;i<len;i++) {
cout << ans[i] << ' ' ;
}
cout << '\n' ;
can = 1 ;
}
return ;
}
if (sum > m) // 已經不可能
return ;
ans[len] = num[idx] ;
dfs(idx+1, sum+num[idx], len+1, ans) ; // 選
dfs(idx+1, sum, len, ans) ; // 不選
return ;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
cin >> n >> m ;
for (int i=0;i<n;i++)
cin >> num[i] ;
sort(num, num+n) ;
vector<int> ans(n) ;
dfs(0, 0, 0, ans) ;
if (!can)
cout << "-1\n" ;
return 0 ;
}
```
最後注意處理未輸出的情況就好，這邊是直接用一個 global var 去處理
## 排列(permutation)
在高中或多或少有被排列組合折磨過，當時有學過定義，將元素打亂後所有可能的序列稱為排序
沒有重複元素的排序是比較簡單的，因為不用考慮重複元素順序的問題，直接排就可以
如果有重複元素的排序就需要考慮相同元素互換位置時等於沒換，排序比較困難
不過一開始我們都不需要考慮這麼多，因為這裡不會講到要怎麼實作排序，而是教函式應用
```cpp=
// 假設 v 是個已排序的 vector，a 是已排序的陣列
do {
// 程式碼片段
} while(next_permutation(a, a+n))
do {
// 程式碼片段
} while(next_permutation(v.begin(), v.end()))
```
這樣整個陣列就可以依照字典序的排列一個個出來，舉個例子，假設矩陣為 $\{1,2,3\}$
$\{1,2,3\} \rightarrow \{1,3,2\} \rightarrow \{2,1,3\} \rightarrow \{2,3,1\} \rightarrow \{3,1,2\} \rightarrow \{3,2,1\}$
## 例題-ZJ d913. 1. 彈珠配置
[題目連結](https://zerojudge.tw/ShowProblem?problemid=d913)
解題思路 :
如果使用枚舉的方式，每次都有新的排列，找到符合條件的第一個答案就可以了
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
vector<int> cnt(6), ans(6) ; // ans 是要做枚舉的陣列
vector<vector<int>> num(6, cnt) ;
for (int i=0;i<6;i++) { // 輸入資料
ans[i] = i+1 ;
for (int j=0;j<6;j++)
cin >> num[i][j] ;
cin >> cnt[i] ;
}
do {
bool now = true ;
for (int i=0;i<6;i++) {
int dis = 0 ; // 與正確答案差幾個
for (int j=0;j<6;j++)
if (ans[j] == num[i][j]) // 相同
dis++ ;
if (dis != cnt[i]) { // 不是答案
now = false ;
break ;
}
}
if (now) { // 答案
for (int i=0;i<6;i++)
cout << ans[i] << ' ' ;
cout << '\n' ;
return 0 ;
}
} while (next_permutation(ans.begin(), ans.end())) ;
return 0 ;
}
```
## 例題-質數
題目敘述:
給定一個整數 $n$，請找出 $n$ 的因數，若 $n$ 的因數只有 $1、n$ 表示 $n$ 為質數
若 $n$ 為質數，請輸出 "prime"，若 $n$ 不是質數，請輸出 "no"，$n \le 10^{14}$
解題思路 :
一般在一秒內通常能運算 $10^7\sim10^8$ 次，所以要保證時間複雜度在這之下
如果這題用暴力枚舉的方式的話，時間複雜度是 $O(n)$，很明顯跑不完
這時候就需要優化枚舉，在數學中學過每個數字的因數都是兩兩一組，比如 $16$
$16$ 可以拆成 $(1,16)、(2,8)、(4,4)$，如果我們只看比較小的那個數字
那範圍甚至可以縮減到 $\sqrt{n}$，這時候時間複雜度就變成 $O(\sqrt{n})$了
```cpp=
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
bool factor(LL n) {
int sn = (int)sqrt(n) ; // 根號 n
for (int i=2;i<sn;i++) // 找是否有其他因數
if (n % i == 0) // 找到非 1、n 的因數
return false ; // 不是質數
return true ; // 沒找到其他因數 -> 是質數
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
LL n ;
cin >> n ;
if (factor(n))
cout << "prime\n" ;
else
cout << "no\n" ;
return 0 ;
}
```
## 例題-ZJ c435. MAX ! MAX ! MAX !
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c435)
解題思路 :
一般來說會以為需要同時枚舉兩個元素，因為要找 `max(a[i]-a[j])`，$i < j$
但其實如果仔細想想，`a[i]` 其實是位置 $j$ 前面的所有元素中值最大的
所以我們不需要在枚舉 `a[i]`，只要枚舉 `a[j]` 的同時更新 `a[i]` 的可能
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
int ans = 0, max_n = -100005, now, n ; // max_n 預設小於最大可能答案
cin >> n ;
for (int i=0;i<n;i++) { // 輸入同時在枚舉 a[j]
cin >> now ;
ans = max(ans, max_n-now) ; // 更新結果
max_n = max(max_n, now) ; // 更新 a[i]
}
cout << ans << '\n' ;
return 0 ;
}
```
## 例題-ZJ h027. 202001_2 矩陣總和
[題目連結](https://zerojudge.tw/ShowProblem?problemid=h027)
解題思路 :
這題是枚舉二維矩陣 $B$ 內的子矩陣，子矩陣大小是固定的，都跟要比較的矩陣 $A$ 相同
所以這裡的枚舉對象應該可以換成一個簡單一點的，也就是矩陣的左上角座標
只要知道矩陣的左上角座標，矩陣的其他位置就可以透過 for-loop 配合矩陣大小找到
然後就是一些運算，確保 $B$ 子矩陣跟 $A$ 同位置不同元素要在 $r$ 個以下
還有計算所以符合條件的子矩陣總和與 $A$ 的絕對差，這裡可以投機取巧一下
因為只有同位置不同元素才會造成總和差異，所以可以只計算它們就好，最後記得取絕對值
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int s, t, n, m, r ;
int A[11][101], B[11][101] ;
int f(int x, int y) {
int dis = 0, cnt = 0 ; // 距離、總和差
for (int i=0;i<s;i++) {
for (int j=0;j<t;j++) {
if (B[x+i][y+j] != A[i][j]) {
cnt += B[x+i][y+j] - A[i][j] ;
if (++dis > r) // 距離太大了
return -1 ; // 這個子矩陣不行
}
}
}
return abs(cnt) ; // 總和差取絕對值
}
int main() {
ios::sync_with_stdio(0), cin.tie(0) ;
cin >> s >> t >> n >> m >> r ;
for (int i=0;i<s;i++) // 輸入
for (int j=0;j<t;j++)
cin >> A[i][j] ;
for (int i=0;i<n;i++) // 輸入
for (int j=0;j<m;j++)
cin >> B[i][j] ;
int ans = INT_MAX, cnt = 0 ; // ans 最小總和絕對差 cnt 有幾個滿足條件
for (int i=0;i+s<=n;i++) {
for (int j=0;j+t<=m;j++) {
int now = f(i, j) ;
if (now != -1) { // 有找到符合條件的
ans = min(ans, now) ;
cnt++ ;
}
}
}
if (cnt == 0) // 沒找到滿足條件的子矩陣
cout << "0\n-1\n" ;
else // 有找到
cout << cnt << '\n' << ans << '\n' ;
return 0 ;
}
```
## 總結
現在介紹的枚舉大部分都是比較簡單的，因為枚舉本身就是比較暴力的解法，只要注意三點
1. 找到適合的枚舉對象，比如之前例題用枚舉矩陣左上角的方式取代枚舉矩陣
2. 讓枚舉的次數減少，通常可以透過固定某些元素、用已知訊息推理元素間關係或剪枝
3. 搭配前置作業讓枚舉過程變順利，之後會講到枚舉搭配其他演算法會讓枚舉更輕鬆
Sign in with Wallet
Connect another wallet