思想

1. 本質(zhì)為兩種搜索順序：

• 枚舉當(dāng)前元素可以放入哪一組
• 枚舉每一組可以放入哪些元素

2. 操作為兩種

• 放入當(dāng)前組
• 新開(kāi)一個(gè)組

---

例題

1. 分成互質(zhì)組

題目鏈接

https://www.acwing.com/problem/content/1120/

題目描述

【解法一】

枚舉每一組可以放哪些元素

#include <iostream>
using namespace std;
const int N = 11;
int g[N][N];
int a[N];
bool st[N];
int n;
int ans = N;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}
bool check(int g[], int x, int k) {for(int i = 0; i < k; i ++)if(gcd(g[i], x) > 1)	return false;return true;
}
void dfs(int gu, int gid, int start, int cnt) {if(gu >= ans)	return ;    //剪枝， 若當(dāng)前分組大于答案，那么不如之前的也沒(méi)必要枚舉了if(cnt == n)	ans = min(ans, gu);bool flag = true;	//從start開(kāi)始找，是否有元素不能入當(dāng)前組for(int i = start; i < n; i ++) {if(!st[i] && check(g[gu], a[i], gid)) {st[i] = true;g[gu][gid] = a[i];dfs(gu, gid + 1, i + 1, cnt + 1);//恢復(fù)現(xiàn)場(chǎng)st[i] = false;flag = false; }} //操作二：新開(kāi)數(shù)組if(flag) dfs(gu + 1, 0, 0, cnt);
}
int main() {cin >> n;for(int i = 0; i < n; i ++)	cin >> a[i];//當(dāng)前在第幾組，第幾個(gè)數(shù)，從哪個(gè)位置開(kāi)始選，已經(jīng)選好幾個(gè)數(shù) dfs(1, 0, 0, 0);	cout << ans; return 0;
}

【解法二】

枚舉當(dāng)前元素可以放入哪個(gè)組

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;const int N = 10;
int a[N];
vector<int> g[N];   //互質(zhì)組
int n;
int ans = N;int gcd(int a, int b){return b?gcd(b, a%b) : a;
}bool check(int c,int x){for(int i=0;i<g[c].size();i++){if(gcd(g[c][i],x)>1) return false;}return true;
}void dfs(int u, int k){ //當(dāng)前為第u個(gè)數(shù)， 已開(kāi)辟的組的個(gè)數(shù)if(u==n){ans=min(ans,k);return;}//每個(gè)元素的方法即 -> 放到當(dāng)前已經(jīng)存在的組中  或者  放到新開(kāi)的組中//操作一：放入已經(jīng)存在的組中for(int i=0; i < k; i ++){if(check(i, a[u])){g[i].push_back(a[u]);dfs(u + 1, k);g[i].pop_back();}}//可見(jiàn)這里的k代表著的是當(dāng)前開(kāi)辟數(shù)組的個(gè)數(shù)//操作二：新開(kāi)一個(gè)組g[k].push_back(a[u]);dfs(u+1, k + 1);g[k].pop_back();
}int main(){cin>>n;for(int i=0;i<n;i++) cin>>a[i];dfs(0, 0);cout<<ans;return 0;
}

---

2. 小貓爬山

題目鏈接

https://www.acwing.com/problem/content/167/

題目描述

輸入樣例：

5 1996
1
2
1994
12
29

輸出樣例：

2

【思路】

第一步很容易會(huì)誤以為這是一道背包問(wèn)題，不過(guò)看了眼數(shù)據(jù)范圍，容量太大，而n的范圍很小，故為一道dfs搜搜問(wèn)題

這里根據(jù)數(shù)據(jù)范圍我們必然需要優(yōu)化，分析可以?xún)?yōu)化的點(diǎn)：

• ① 要求最小車(chē)輛，那么如果我們搜索某種決策時(shí)當(dāng)前的車(chē)輛數(shù)已經(jīng)大于ans了，那么必然不是最優(yōu)解，直接退出即可
• ② 對(duì)于dfs決策時(shí)，要想使得決策的分支少點(diǎn)，那么從根開(kāi)始越少的話，那么必然分支也會(huì)更少，想到從此處進(jìn)行優(yōu)化的話，那么若是優(yōu)先考慮重量大的，可以實(shí)現(xiàn)，因?yàn)樵谝延械能?chē)輛中選擇可放入的重量大的可選車(chē)輛少

下面展示代碼：

【W(wǎng)A代碼】

枚舉每一組可以放入哪些元素

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n, W;
int w[N];
int g[N][N];
bool st[N];
int ans = N;void dfs(int gu, int ct, int start, int cnt) {if(gu >= ans)	return ;if(cnt == n) {ans = min(ans, gu);return;}bool flag = true;	//判斷是否可以放進(jìn)去當(dāng)前組//操作一：加入當(dāng)前組 for(int i = start; i < n; i ++) {if(!st[i] && ct + w[i] <= W) {st[i] = true;dfs(gu, ct + w[i], start + 1, cnt + 1);//恢復(fù)現(xiàn)場(chǎng)st[i] = false; flag = false;}}//操作二：新開(kāi)組if(flag) 	dfs(gu + 1, 0, 0, cnt);}int main() {cin >> n >> W;for(int i = 0; i < n; i ++)	cin >> w[i];	//為了使得決策少點(diǎn)，優(yōu)化時(shí)間，選擇先放重量大的sort(w, w + n, greater<int>());//從第gu個(gè)組開(kāi)始，當(dāng)前在判斷第gid個(gè)數(shù)，已經(jīng)匹配的數(shù)字， 從哪個(gè)數(shù)開(kāi)始 dfs(1, 0, 0, 0);cout << ans;return 0;
}

【AC代碼】

枚舉當(dāng)前元素可以放入哪些組

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n, W;
int w[N];
int sum[N]; //第i輛車(chē)的重量
bool st[N];
int ans = N;void dfs(int u, int k) {    //u代表當(dāng)前遍歷的數(shù)，k代表當(dāng)前已有分組數(shù)量if(k >= ans)    return;if(u == n)  {// ans = min(ans, k);   //因?yàn)橛猩喜綏l件制約，故不需要minans = k;return;}   //操作一：放入某個(gè)已有的車(chē)輛for(int i = 0; i < k; i ++) {if(sum[i] + w[u] <= W) {sum[i] += w[u];dfs(u + 1, k);//恢復(fù)現(xiàn)場(chǎng)sum[i] -= w[u];}}//操作二： 放不下，新開(kāi)車(chē)輛sum[k] = w[u];dfs(u + 1, k + 1);sum[k] = 0;}int main() {cin >> n >> W;for(int i = 0; i < n; i ++)	cin >> w[i];	//為了使得決策少點(diǎn)，優(yōu)化時(shí)間，選擇先放重量大的sort(w, w + n, greater<int>());dfs(0, 0);cout << ans;return 0;
}