剪枝

將搜索過程中一些不必要的部分剔除掉，因為搜索過程構成了一棵樹，剔除不必要的部分，就像是在樹上將樹枝剪掉，故名剪枝。

剪枝是回溯法中的一種重要優化手段，方法往往先寫一個暴力搜索，然后找到某些特殊的數學關系，或者邏輯關系，通過它們的約束讓搜索樹盡可能淺而小，從而達到降低時間復雜度的目的。

一般來說剪枝的復雜度難以計算。

例題

藍橋oj2942數字王國之軍訓排隊

問題描述

數字王國開學了，它們也和我們人類一樣有開學前的軍訓，現在一共有 n 名學生，每個學生有自己的一個名字 ai?（數字王國里的名字就是一個正整數，注意學生們可能出現重名的情況），此時叛逆教官來看了之后感覺十分別扭，決定將學生重新分隊。

排隊規則為：將學生分成若干隊，每隊里面至少一個學生，且每隊里面學生的名字不能出現倍數關系（注意名字相同也算是倍數關系）。

現在請你幫忙算算最少可以分成幾隊？

例：有 4 名學生 (2,3,4,4)，最少可以分成 (2,3)、(4)、(4) 共 3 隊。

輸入格式

第一行包含一個正整數 n，表示學生數量。

第二行包含 n 個由空格隔開的整數，第 i 個整數表示第 i 個學生的名字 ai?。

輸出格式

輸出共 1 行，包含一個整數，表示最少可以分成幾隊。

樣例輸入

4
2 3 4 4

樣例輸出

3

解1.不剪枝

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 15;
int a[N],n;vector<int>v[N];//v[i]表示第i組里面所有人的編號//cnt表示隊伍數量，dfs返回在cnt個隊伍的情況下是否可以成功分組bool dfs(int cnt, int dep)
{if (dep == n + 1){//說明每個人都成功分組了//檢查當前方案的合法性for (int i = 1; i <= cnt; i++)//每個隊伍枚舉里面所有的二元組{for (int j = 0; j < v[i].size(); j++){for (int k = j+1; k < v[i].size(); k++){if (v[i][k] % v[i][j] == 0)return false;}}}return true;}//枚舉每個人所屬的隊伍for (int i = 1; i <= cnt; i++){v[i].push_back(a[dep]);if (dfs(cnt, dep + 1))return true;//恢復現場v[i].pop_back();}return false;
}int main()
{// 請在此輸入您的代碼cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + 1 + n);//枚舉n個for (int i = 1; i <= n; i++){if (dfs(i, 1))//i個隊伍，從第一層開始搜索，看這種情況是否可以裝的下（即成功分組）{cout << i << endl;break;}}return 0;
}

解2.剪枝（我沒太懂，先放著）

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 15;
int a[N],n;vector<int>v[N];//v[i]表示第i組里面所有人的編號//cnt表示隊伍數量，dfs返回在cnt個隊伍的情況下是否可以成功分組bool dfs(int cnt, int dep)
{if (dep == n + 1){//說明每個人都成功分組了//檢查當前方案的合法性for (int i = 1; i <= cnt; i++)//每個隊伍枚舉里面所有的二元組{for (int j = 0; j < v[i].size(); j++){for (int k = j+1; k < v[i].size(); k++){if (v[i][k] % v[i][j] == 0)return false;}}}return true;}//枚舉每個人所屬的隊伍for (int i = 1; i <= cnt; i++){bool tag = true;
for(const auto &j:v[i])if (a[dep] % j == 0){tag = false;break;}
if (!tag)continue;v[i].push_back(a[dep]);if (dfs(cnt, dep + 1))return true;//恢復現場v[i].pop_back();}return false;
}int main()
{// 請在此輸入您的代碼cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + 1 + n);//枚舉n個for (int i = 1; i <= n; i++){if (dfs(i, 1))//i個隊伍，從第一層開始搜索，看這種情況是否可以裝的下（即成功分組）{cout << i << endl;break;}}return 0;
}

?