常用的几种剪枝策略
1.优化搜索顺序
大部分情况下 我们应该优先搜索分支较少的节点
例如 分组问题 可以先从花费较大的元素搜索 可以减少状态分支
2.排除等效冗余
如果不考虑顺序的话 尽量用组合的方式搜索 即与组内元素顺序无关
3.可行性剪枝
在搜索过程中已经检测到不合法 可以提前退出
4.最优性剪枝
在搜搜过程中 已经检测到当前答案大于最优解 可以提前退出
5.记忆化搜索(DP)
AcWing165. 小猫爬山
翰翰和达达饲养了N只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为W，而N只小猫的重量分别是C 1 、 C 2 … … C N
当然，每辆缆车上的小猫的重量之和不能超过W。
每租用一辆缆车，翰翰和达达就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？
输入格式
第1行：包含两个用空格隔开的整数，N和W。
第2…N+1行：每行一个整数，其中第i+1行的整数表示第i只小猫的重量Ci
输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。
数据范围
1 ≤ N ≤ 18
1 ≤ C i ≤ W ≤ 1 0 8
剪枝策略
优化搜索顺序 从较重的小猫开始搜索
可行性剪枝 遇到大于当前最优解的 直接return
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<cmath> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<int, string>PIS; typedef pair<int, PII>PIII; const int N = 20; int w[N], sum[N]; int res = INF; int n, W; bool cmp(int a, int b) { return a > b; } void dfs(int u, int k) { if (k >= res)return; if (u == n) { res = k; return; } bool flag = true; for (int i = 0; i < k; ++i) { if (sum[i] + w[u] <= W) { flag = false; sum[i] += w[u]; dfs(u + 1, k); sum[i] -= w[u]; } } sum[k] += w[u]; dfs(u + 1, k + 1); sum[k] -= w[u]; } int main() { cin >> n >> W; for (int i = 0; i < n; ++i)scanf("%d", &w[i]); sort(w, w + n, cmp); dfs(0, 0); cout << res << endl; }
AcWing166. 数独
数独是一种传统益智游戏，你需要把一个9 × 9的数独补充完整，使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含81个字符，代表数独的81个格内数据（顺序总体由上到下，同行由左到右）。
每个字符都是一个数字（1-9）或一个”.”（表示尚未填充）。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词“end”的单行，表示输入结束。
输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。
剪枝策略
位运算
优化搜索顺序 从能填的数较少的位置开始搜 减少每个情况的分支个数
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<cmath> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<int, string>PIS; typedef pair<int, PII>PIII; const int N = 9, M = 1 << N; int ones[M], maps[M]; int cell[3][3]; int row[N], col[N]; char str[100]; void draw(int x, int y, int t, int is_set) { if (is_set)str[x * N + y] = '1' + t; else str[x * N + y] = '.'; int v = 1 << t; if (!is_set)v = -v; row[x] -= v; col[y] -= v; cell[x / 3][y / 3] -= v; } void init() { for (int i = 0; i < N; ++i)row[i] = col[i] = (1 << N) - 1; for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) cell[i][j] = (1 << N) - 1; } int get_(int x, int y) { return col[y] & row[x] & cell[x / 3][y / 3]; } bool dfs(int cnt) { if (!cnt)return true; int minn = 10; int x, y; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (str[i * N + j] == '.') { int state = get_(i, j); if (ones[state] < minn) { minn = ones[state]; x = i, y = j; } } } } int state = get_(x, y); for (int i = state; i; i -= lowbit(i)) { int t = maps[lowbit(i)]; draw(x, y, t, true); if (dfs(cnt - 1))return true; draw(x, y, t, false); } return false; } int main() { for (int i = 0; i < N; ++i)maps[1 << i] = i; for (int i = 0; i <1 << N; ++i) { for (int j = 0; j < N; ++j) { ones[i] += i >> j & 1; } } while (cin >> str && str[0] != 'e') { init(); int cnt = 0; for (int i = 0, k = 0; i < N; ++i) { for (int j = 0; j < N; ++j,++k) { if (str[k] != '.') { int t = str[k] - '1'; draw(i, j, t, true); } else cnt++; } } dfs(cnt); puts(str); } }
AcWing167. 木棒
乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序，帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
输入格式
输入包含多组数据，每组数据包括两行。
第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。
第二行是截断以后，所得到的各节木棍的长度。
在最后一组数据之后，是一个零。
输出格式
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。
数据范围
数据保证每一节木棍的长度均不大于50。
剪枝策略
可行性剪枝：木棒的长度一定是木棍长度总和的因子
优化搜索顺序：按木棍长度从大到小枚举 减少分支
排除等效冗余：①按照组合数方式枚举（木棒内部的木棍顺序无所谓）
② 并且如果当前木棍不能加入到木棒中 那么略过后面所有与之长度相等的木棍
③ 如果是木棒的第一根木棍放入失败 则一定失败
④ 如果当前木棍放在木棒最后一个位置失败了 则一定失败
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<cmath> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<int, string>PIS; typedef pair<int, PII>PIII; const int N = 70; int n, sum, length; int w[N]; bool vis[N]; bool cmp(int a, int b) { return a > b; } bool dfs(int u, int s, int start) { if (u * length == sum)return true; if (s == length)return dfs(u + 1, 0, 0); for (int i = start; i < n; ++i) { //可行性剪枝 if (vis[i])continue; if (s + w[i] > length)continue; vis[i] = true; if (dfs(u, s + w[i], i + 1))return true; vis[i] = false; //剪枝3.3 if (!s)return false; //剪枝3.4 if (s + w[i] == length)return false; //剪枝3.2 int j = i; while (j < n && w[j] == w[i])++j; i = j - 1; } return false; } int main() { while (cin >> n, n) { length = 1; sum = 0; memset(vis, false, sizeof vis); for (int i = 0; i < n; ++i) { scanf("%d", &w[i]); sum += w[i]; } sort(w, w + n, cmp);// 优化搜索顺序 while (1) { if (sum % length == 0 && dfs(0, 0, 0)) { cout << length << endl; break; } length++; } } return 0; }
AcWing168. 生日蛋糕
7月17日是M r . W 的生日，A C M − T H U为此要制作一个体积为N π 的M层生日蛋糕，每层都是一个圆柱体。
设从下往上数第i层蛋糕是半径为R i , 高度为H i 的圆柱。
当i < M时，要求R i > R i + 1 且H i> H i + 1 。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q = S π ，请编程对给出的N和M，找出蛋糕的制作方案（适当的R i 和H i 的值），使S最小。
除Q外，以上所有数据皆为正整数 。
输入格式
输入包含两行，第一行为整数N（N <= 10000），表示待制作的蛋糕的体积为N π 。
第二行为整数M(M <= 20)，表示蛋糕的层数为M。
输出格式
输出仅一行，是一个正整数S（若无解则S = 0）。
数据范围
1≤N≤10000
1≤M≤20
剪枝策略
优化搜索顺序：从底到上搜索 先占大块的体积 并且对于R和H 先从大到小枚举R 因为R 2
是平方级 再从大到小枚举H
可行性剪枝：①：假设当前层数为u 则u ≤ R ( u ) ≤ R ( u + 1 ) − 1 因为每一层的半径严格递减并且为整数
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<cmath> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<int, string>PIS; typedef pair<int, PII>PIII; const int N = 25; int n, m; int R[N], H[N]; int minv[N], mins[N]; int ans = INF; void dfs(int u, int v, int s) { if (v + minv[u] > n)return; if (s + mins[u] >= ans)return; if (s + 2 * (n - v) / R[u + 1] >= ans)return; if (!u) { if (v == n)ans = s; return; } for (int r = min(R[u + 1] - 1, (int)(sqrt(n - v))); r >= u;--r) { for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; --h) { int t = 0; if (u == m)t = r * r; R[u] = r, H[u] = h; dfs(u - 1, v + r * r * h, s + 2 * r * h + t); } } } int main() { cin >> n >> m; for (int i = 1; i <= m; ++i) { minv[i] = minv[i - 1] + i * i * i; mins[i] = mins[i - 1] + 2 + i * i; } if (minv[m] > n) { puts("0"); return 0; } R[m + 1] = H[m + 1] = INF; dfs(m, 0, 0); cout << ans << endl; }
