您现在的位置是:首页 >其他 >算法提高-搜索-DFS之剪枝与优化网站首页其他
算法提高-搜索-DFS之剪枝与优化
简介算法提高-搜索-DFS之剪枝与优化
DFS之剪枝与优化
AcWing 165. 小猫爬山
DFS的五种剪枝方法
(1)优化搜索顺序
(2)排除等效冗余
(3)可行性剪枝
(4)最优性剪枝
(5)记忆化搜索(这个放在dp里面说了)
下面这题涉及三个剪枝
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n;
int maxW;
int sum[N];
int w[N];
int ans = N;//这里debug很久,题目找的是最小值,初始化的时候要给他定义一个最大值
void dfs(int u, int k)
{
// (3)最优性剪枝
if (k >= ans) return ;
if (u == n)
{
ans = k;
return ;
}
//1.判断能否加入现在已经存在的缆车
//遍历缆车
for (int i = 0; i < k; i ++ )
{
// (2)可行性剪枝
if (sum[i] + w[u] <= maxW)
{
sum[i] += w[u];
dfs(u + 1, k);
sum[i] -= w[u];//回溯
}
}
//2.判断是否需要新开一个缆车
sum[k] = w[u];//因为我们缆车的下标是从0开始的
dfs(u + 1, k + 1);
//sum[k] = 0; sum是全局变量,但这不是sum += w[u],其实不用回溯,我们返回到k - 1层的时候会直接重新赋值覆盖sum[k]
}
int main()
{
cin >> n >> maxW;
for (int i = 0; i < n; i ++ ) cin >> w[i];
// (1)优化搜索顺序
sort(w, w + n);
reverse(w, w + n);
dfs(0, 0);
cout << ans;
return 0;
}
AcWing 166. 数独
AcWing 167. 木棒
6种剪枝方法:1, 2, 3-1, 3-2, 3-3, 3-4
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 64 + 5;
int sum;//所有小棒加起来的总长度,也是所有大棒加起来的总长度
int length;//枚举每一根大棒的长度
int n;
int stick[N];//记录每根木棍的长度
int st[N];
bool dfs(int u, int cur, int start)
{
if (u * length == sum) return true;//找到一组满足题意的解
if (cur == length) return dfs(u + 1, 0, 0);//第u根木棒组合完毕,枚举第u+1根,直到u * length == sum才代表满足题意
for (int i = start; i < n; i ++ )
{
if (st[i]) continue;
if (stick[i] + cur > length) continue;//可行性剪枝
st[i] = true;
if (dfs(u, cur + stick[i], i + 1)) return true;//这一步相当编译器帮我们回溯
st[i] = false;//手动回溯
//剪枝 3-3 和 3-4,
//走到了这一步说明之前dfs return false了,我们判断一下是将小棍放在大棍的哪个位置失败了
//根据3-3和3-4,如果是放在大棍的第一个位置和放在大棍的最后一个位置失败了,那么就直接不同继续判断下去了
//当前这个小棍stick[i]也一定不能放在后续的其他大棍中,必找不到一组合法解
if (cur == 0 || cur + stick[i] == length) return false;
//剪枝3-2如果当前的小棍失败了,那么略过枚举stick[]中后面和它长度一样的小棍
int j = i + 1;
while (j < n && stick[j] == stick[i]) j ++ ;
i = j - 1;//上面的while能退出说明stick[i]已经!=stick[j]了,所有要 -1
}
return false;
}
int main ()
{
while (cin >> n, n != 0)
{
//多组数据,sum和st要置0
memset(st, 0, sizeof st);
sum = 0;
for (int i = 0; i < n; i ++ )
{
cin >> stick[i];
sum += stick[i];
}
sort(stick, stick + n);//优化搜索顺序,先枚举长的木棒,这样后面需要搜索的分支可以减少些
reverse(stick, stick + n);
length = 1;
while (true)
{
if (sum % length == 0 && dfs(0, 0, 0))
{
cout << length << endl; //题目求的是原始木棒的最小长度,因此我们length从1开始枚举即可,只要找到一组合法的解就break
break;
}
length ++ ;//走到这一步了说明之前没break没找到一组合法的解,那么继续枚举
}
}
return 0;
}
AcWing 168. 生日蛋糕
这题挺难的,我反正糊着写完了建议配合y总讲解和这篇题解复习
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int M = 25, INF = 1e9;
int n, m;
int R[M], H[M];//记录每一层的半径和高度
int minv[M], mins[M];//记录前i层的最小体积和,最小面积和
int ans = INF;
void dfs(int u, int v, int s)
{
//可行性剪枝
if (v + minv[u] > n) return ;
if (s + mins[u] >= ans) return ;
//这个是用公式推出来的1-u层蛋糕的面积的最小值
if (s + 2 * (n - v) / R[u + 1] >= ans) return ;
if (u == 0)//倒着枚举的,所以在第0层收集结果
{
if (v == n) ans = s;//前面没return,说明这里的s一定小于ans,直接赋值就行了,我们这里的ans一定是最小的
return ;//这个return不能放在if里面,因为也许u == 0的时候v!=n,return要是放在里面如果无解就会TLE
}
//优化搜索顺序,r是二次方的,先搜r再搜h,分支会少
for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r -- )//min函数一定要都是int,所以要强转
for (int h = min(H[u + 1] -1, n - v / r / r); h >= u; h -- )//倒着枚举的要--
{
//特判一下,如果是m层我们直接加上整个上表面积就行,后面再枚举每个侧表面积
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);//2 * r * h是这一层的侧面积,t是特判出来的上表面积,就是一整个圆盘,一组解只要加1次就行
}
}
int main ()
{
cin >> n >> m;
//预处理
for (int i = 1; i <= m; i ++ )
{
minv[i] = minv[i] + i * i * i;//r * r * h
mins[i] = mins[i] + 2 * i * i;//2 * r * r ,题目说了方便计算pi省略
}
//m+1层不存在,作为哨兵,减少边界情况的判断
R[m + 1] = H[m + 1] = INF;//不加这个会报Float Point Exception,但这个y总说是除0了
//优化搜索顺序,先从最大的一层搜,分支会少
dfs(m, 0, 0);
if (ans == INF) ans = 0;//特判无解的情况
cout << ans;
return 0;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。