###### tags: `MDCPP` #### MDCPP進階組講義05 ## 遞迴枚舉(回溯法) 作者：LittlePants ---- ---- ## 遞迴枚舉可以解決一切 ## 但必須等到世界毀滅 BY 吳邦一 ---- ## 甚麼是枚舉? - 就是把所有可能都列出來 - 是最暴力的作法 - 但每看到一個題目可以先想想要怎麼枚舉 - 再想想看有沒有更好的方法 ---- ## 為甚麼要用遞迴來枚舉? - 因為很好寫 - 因為可以增加剪枝條件，時間複雜度不比不用遞迴差 --- ## 常見的枚舉 --- ## 子集枚舉(Subset) ---- ## 甚麼是子集? - 給你若干個物品，你可以從裡面選任意個(也可以不選) - 你選出來的那些物品就稱為一個子集 ---- - 假設有 n 個物品，我們就會有 $2^n$ 種選法 - 因為每個物品只有選或不選兩種狀態 ---- ## 要怎麼枚舉? - 因為我們要枚舉所有可能，所以時間複雜度一定會大於 $O(2^n)$ - 所以通常只有 n 不大於 30 的時候會用 - 每種物品都只有選或不選 - 我們可以畫一棵遞迴決策樹來看看他是如何運作的 ---- ## 例題 [Apple Division](https://cses.fi/problemset/task/1623) ---- ## 題目大意 有 $n$ 堆蘋果，$p_1\ p_2$ ~ $p_n$。 你要把蘋果分成任意兩堆，使兩堆的蘋果數量差最少。 $n <= 20$, $p_i <= 10^9$ ---- ## 想法 - 因為 $n$ 非常小會很直覺得想到可以枚舉 - 如果 $p_i$ 範圍沒這麼大，可以使用背包dp ---- ## 解題思路 - 我們可以直接枚舉子集 - 但題目說要分成兩堆 - 我們只需要把 全部減掉現在枚舉的子集 就會得到另一堆了 ---- ### 參考Code ```cpp= int a[25], n, ans, total; void dfs(int u, int sum){ if(ans == 0 || 2 * sum > total + ans) return; // prune 剪枝 if(u == n){ ans = min(ans, abs(2 * sum - total)); // 枚舉完所有物品 遞迴結束條件 return; } dfs(u + 1, sum + a[u]); // 選 dfs(u + 1, sum); // 不選 } signed main(void){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0; i < n; i++) cin >> a[i], total += a[i]; ans = 1e18; dfs(0, 0); cout << ans << '\n'; } ``` --- ## 更多例題 [NPSC初賽 分裁判問題](http://mdcpp.mingdao.edu.tw/problem/C014) [女中judge 以物易物](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b040) [At coder 切竹子](https://atcoder.jp/contests/abc119/tasks/abc119_c) --- ## 枚舉排列 ---- ## 例題 [小數的密碼](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b037) ---- ---- ## 題目大意 密碼是 n 位數，且只包含數字 1 ~ m 按照字典序排列，輸出所有密碼的可能 $n <= 10$, $m <= 9$ ---- ## 思考 先想一下複雜度，有 n 位數每個位數都有 m + 1 種可能 所以複雜度 $O(n^{m+1})$ 感覺不太對?! 這樣是 $O(10^{10})$ ㄟ? 應該是出題者複雜度沒算好，其實測資很弱 ---- ## 解題思路 - 這個感覺用for迴圈就可以解ㄟ，但如果你試了就會發現困難重重 - 而且這題要求按照字典序排列，用遞迴寫會很方便 - 我們可以使用遞迴搭配for迴圈來完成這題 ---- ### 參考Code ```cpp= #include<iostream> using namespace std; int n, m, path[100001]; void backtrack(int level){ // level 代表現在枚舉到第幾位數 if(level == n){ // 終止條件 順便輸出 for(int i = 0 ; i < n; i++) cout << path[i]; cout << '\n'; return; } for(int i = 0; i <= m; i++){ path[level] = i; backtrack(level + 1); } } int main(void){ cin >> n >> m; backtrack(0); } ``` ---- ---- ## 變化題 [全排列](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b038) ---- ## 想法 跟上一題的差別就在於數字不能重複出現 所以就開一個陣列紀錄那些數字已經出現過就好了 ---- ```cpp= #include<iostream> #include<bitset> using namespace std; int n, path[15]; bitset<15> used; // 用來記錄那些數字被用過了 void backtrack(int level){ if(level == n){ for(int i = 0 ; i < n; i++) cout << path[i]; cout << '\n'; return; } for(i = 1; i <= n; i++){ if(used[i]) continue; used[i] = 1; backtrack(level + 1); used[i] = 0; } } int main(void){ cin >> n; backtrack(0); } ``` ---- ## 練習題 [全排列 MD judge](http://mdcpp.mingdao.edu.tw/problem/B010) ---- 參考 Code :::spoiler ```cpp= #include<iostream> #include<bitset> using namespace std; int n, path[20], lim[20]; bitset<20> used, f; void backtrack(int level){ if(level == n){ for(int i = 0 ; i < n; i++) cout << path[i] << " "; cout << '\n'; return; } int t = 1; if(f[level] == 0){ t = lim[level]; f[level] = 1; } for(int i = t; i <= n; i++){ if(used[i]) continue; used[i] = 1; backtrack(level + 1); used[i] = 0; } } int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0; i < n; i++) cin >> lim[i]; backtrack(0); } ``` ::: --- ## 八皇后問題 ---- ## 例題 [Chessboard and Queens](https://cses.fi/problemset/task/1624) ---- ## 觀察棋盤 - 同一直行橫列都很好判斷 - 但斜線怎麼辦? ---- - 其實規律應該不難發現(可以把它當作直角座標系) - 圖片 ---- - 知道了這些條件之後就只需要枚舉就可以了耶! - 遇到可以擺皇后的地方就先擺，擺到不能擺為止 - 如果擺滿 n 個那就是符合條件 ---- ## 策略 - 所以要一格一格枚舉嗎? - 其實不用先枚舉一列，再從裡面選一個出來就好 - 如果這一列已經放了就直接到下一列 - 如果 1 ~ n 列都有擺，那就是一組解 ---- 參考 Code :::spoiler https://cses.fi/paste/7c12490e107cd16f157639/ ::: ---- ## 額外練習 1. [數獨](https://zerojudge.tw/ShowProblem?problemid=d263) 2. [得分最多的皇后](http://mdcpp.mingdao.edu.tw/problem/b039) --- ### 遞迴枚舉的經典題如下 - 子集枚舉(subset) - 排列組合的枚舉 - 八皇后問題 - 需要取消操作的遞迴(走迷宮問題) - 需要得迴圈層數是變數 ---- ## 總結 雖然枚舉是最差的方法，但逼不得已時還是要會用 而且枚舉常常有助於你對題目的了解 對一個題目先了解怎麼枚舉，再去優化他 枚舉搭配一些技巧，其實複雜度也不會到太差 --- ## 感謝觀看