【搜索】DFS剪枝与优化
剪枝是什么意思呢？
我们知道，不管是内部搜索还是外部搜索，都可以形成一棵搜索树，如果将搜索树全部遍历一遍，效率会很低，但如果我们能在搜索的过程中，提前预知，判断某一些不可能是正确答案的情况，就可以不用遍历其下的子树，从而提高我们的算法效率
我们可以从以下几个角度考虑剪枝：
- 优化搜索顺序
优先选择分支较少的结点 - 排除等效冗余
尽量保证不搜索重复的状态（就是在不考虑顺序时，采用组合的方式搜索） - 可行性剪枝
不合法提前退出 - 最优性剪枝
如果当前答案无论如何都比目前的最优解要差，那就可以不要往下搜了 - 记忆化搜索（DP）
接下来将通过例题来讲解
小猫爬山
翰翰和达达饲养了 N 只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。
当然，每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？
输入格式
第 1 行：包含两个用空格隔开的整数，N 和 W。
第 2..N+1 行：每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。
输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。
数据范围
1 ≤ N ≤ 18,
1 ≤ C~i~ ≤ W ≤ 108
输入样例5 1996
1
2
1994
12
29
输出样例2
题意
给出小猫重量、缆车承重，问最少要多少缆车能把所有小猫运走
思路
枚举每只小猫，有两种状态：
- 放到当前这辆车上
- 新开一辆车
优化：
- 优化搜索顺序：比较一只比较轻的猫和另一只比较重的猫，显然是比较重的猫带来的分支数量较少，因为如果猫非常重可以直接把车占满，但是猫很轻的话我们就要考虑还要加什么别的猫，因此：将所有猫按从大到小排序，优先放重猫
- 可行性剪枝：当发现目前小猫的重量已经超过缆车承重，就不要再往下搜了
- 最优性剪枝：当发现目前缆车数量已经大于等于当前计算出的缆车最少数量，就不要再搜索了
代码
using namespace std;
const int N = 20;
int n, m;
int w[N];
int sum[N];
int ans = N; // 最坏的情况:每只小猫占一辆车
void dfs(int u, int k) // u:当前在搜第几只猫 k:当前在搜第几辆车
{
// 最优性剪枝
if (k >= ans) return;
if (u == n)
{
ans = k;
return;
}
for (int i = 0; i < k; i ++ ) // 遍历每一辆车
// 可行性剪枝
if (sum[i] + w[u] <= m) // 称重符合条件
{
sum[i] += w[u];
dfs(u + 1, k);
sum[i] -= w[u]; // 恢复现场
}
// 新开一辆车
sum[k] = w[u];
dfs(u + 1, k + 1);
sum[k] = 0; // 恢复现场
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> w[i];
// 优化搜索顺序
sort(w, w + n);
reverse(w, w + n);
dfs(0, 0);
cout << ans << '\n';
}数独
原题链接
数独是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行，包含 81 个字符，代表数独的 81 个格内数据（顺序总体由上到下，同行由左到右）。
每个字符都是一个数字（1−9）或一个 .（表示尚未填充）。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词 end 的单行，表示输入结束。
输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。
输入样例4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936
题意
填好数独，保证每行每列、每个3x3方块都包含1-9
思路
先做一个小优化，看比如说一个3x3小方格中有哪些数字没被用过，随意选择一个格子，然后对这些数字依次枚举搜索即可
优化：
- 优化搜索顺序：选择格子时，尽量选择分支数量较少的格子，比如说一个格子有2种填法，另一个格子有5种，那肯定优先选择2种的
- 可行性剪枝：一旦与行列九宫格重复时就不要继续搜了
- ==位运算优化：== 特殊优化，可以用一个九位的二进制数表示每一行数使用的状态
比如：0 1 0 0 1 1 1 0 0 可以用来表示2 5 6 7还没用其他数字用过了
我们考虑这一位上能不能填这个数时，应该考虑二进制数的交集，即在行、列、九宫格的二进制数列上，这个数字都为1，表示在行、列、九宫格内这个数字都没有被使用，我们才能用这个数（直接按位与&）
这里有个比循环九次更好的办法——lowbit
lowbit运算可以帮助我们在O(1)的时间复杂度内，返回当前数里的最后一个1，因此用lowbit循环就可以抠出来所有的1
好难啊好难啊qaq看代码注释吧还是
代码
|
木棒
乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序，帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
输入格式
输入包含多组数据，每组数据包括两行。
第一行是一个不超过 64 的整数，表示砍断之后共有多少节木棍。
第二行是截断以后，所得到的各节木棍的长度。
在最后一组数据之后，是一个零。
输出格式
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。
数据范围
数据保证每一节木棍的长度均不大于 50。
输入样例9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例6
5
题意
给出一些数，将其分成若干组，使每一组总和相等，问最小的总和是多少
思路
木棒：每一组的总和
木棍：题目中输入的数据
先从小到大枚举木棒的长度length，看木棍能不能组成该长度的木棒
优化：
- 所有木棍的总长度sum必须能整除木棒的长度length，才可能有解，不能整除的情况直接回溯不要搜了
- 优化搜索顺序：先枚举比较长的木棍，使之后的分支较少
- 排除等效冗余：
(1) 如果一根木棒里有第一根第二根两根木棍，那么先用第一根和先用第二根达成的效果都是一样的，因此按照组合数方式枚举
(2) 如果当前木棍加到当前木棒中失败，那直接略过后面所有等长木棍
(3) 如果是木棒的第一根木棍失败（说明这根木棍没地方放），则当前状态一定失败，直接回溯不要往下搜了
(4) 如果是木棒的最后一根木棍失败（这里的意思是往下dfs找不到解），则当前状态一定失败（因为放入比这根木棍小的木棍拼接起来的也一定找不到解），直接回溯不要往下搜了代码
using namespace std;
const int N = 70;
int n;
int w[N], sum, length; // w[i]:每根小棍长度 sum:所有小棍总长度 length:每组总和
bool st[N]; // 小棍有没有用过
bool dfs(int u, int s, int start) // u:当前枚举到哪根大棍 s:当前大棍长度 start:开始位置
{
if (u * length == sum) return true; // 符合条件
if (s == length) return dfs(u + 1, 0, 0); // 这根木棍长度已达要求，开下一根木棍
// 优化3(1):从start开始枚举
for (int i = start; i < n; i ++ ) // 从start开始遍历木棍
{
if (st[i]) continue; // 已遍历
if (s + w[i] > length) continue; // 可行性剪枝
st[i] = true; // 更改状态
if (dfs(u, s + w[i], i + 1)) return true; // 下一层遍历
st[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()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
while (cin >> n, n)
{
memset(st, false, sizeof st);
sum = 0;
for (int i = 0; i < n; i ++ )
{
cin >> w[i];
sum += w[i];
}
// 优化2：搜索顺序
sort (w, w + n);
reverse(w, w + n);
length = 1;
while (1)
{
// 优化1:必须是整数倍
if (sum % length == 0 && dfs(0, 0, 0))
{
cout << length << '\n';
break;
}
length ++ ;
}
}
}生日蛋糕
原题链接
7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 Nπ 的 M 层生日蛋糕，每层都是一个圆柱体。
设从下往上数第 i 层蛋糕是半径为 Ri，高度为 Hi 的圆柱。
当 $i
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 Q 最小。
令 $Q=Sπ$ ，请编程对给出的 N 和 M，找出蛋糕的制作方案（适当的 Ri 和 Hi 的值），使 S 最小。
除 Q 外，以上所有数据皆为正整数。
输入格式
输入包含两行，第一行为整数 N，表示待制作的蛋糕的体积为 Nπ。
第二行为整数 M，表示蛋糕的层数为 M。
输出格式
输出仅一行，是一个正整数 S（若无解则 S=0）。
数据范围
1 ≤ N ≤ 10000,
1 ≤ M ≤ 20
输入样例100
2
输出样例68
题意
多层蛋糕，给出总体积总层数，可以自定义每一层半径和高度，使得从上往下看的总面积和总侧面积之和最小，求最小值
思路
首先明确我们的目的是让 2 R~m~ h~m~ + 2 R~m-1~ h~m-1~ + … + 2 R~1~ h~1~ + R~m~^2^ 最小（省去了所有的$π$）
优化：
- 优化搜索顺序：分支少的先搜，从大到小枚举
(1) 要先搜面积大的，因此自底向上搜
(2) 半径是平方级别，高是一次方，半径对体积影响更大，因此先枚举半径 - 可行性剪枝：
(1) 设从上往下为1-m层，第 u 层的半径记为 R~u~，一定比 u 大，且比 R~u+1~ - 1 小，同时，我们设第 u 层下方的所有体积为 V，那么前 u 层的体积就是 $n - V$，即有 $n - V >= R_u^2h_u$，放缩后有 $R_u <= \sqrt{n - V}$
据此得到：==$u <= R_u <= min\{R_{u+1}-1, \sqrt{n-V}\}$==
(2) 同时，H~u~也>=u，且比 H~u+1~小， $n - V >= R_u^2h_u$，放缩后有 $h_u<= \frac{n-V}{R^2}$
据此得到：==$u <= h_u <= min\{h_{u+1}-1, \frac{n-V}{R^2}\}$== - 最小体积是半径和高都取1时，因此可以预处理一下前 u 层的体积最小值$minv(u)$和表面积最小值$mins(u)$，需要满足以下两个条件才有往下搜的必要，否则直接回溯：
==$V+minv(u)<=n$==
==$s+mins(u)<ans$== - 已知：$n-V=\sum_{k=1}^{u}R_k^2h_k$
并且：$S_{1\rightarrow u}=\sum_{k=1}^{u}2R_kh_k=\frac{2}{R_{u+1}}\sum_{k=1}^{u}R_uhR_{u+1}>\frac{2}{R_{u+1}}\sum_{k=1}^{u}R_u^2h$
因此：$S_{1\rightarrow u}>\frac{2(n-V)}{R_{u+1}}$
所以当$s+\frac{2(n-V)}{R_{u+1}}>=ans$时，已经不可能是最优解了，直接回溯
(好难…疯掉TAT
代码
|
微信- 支付宝
