剪枝是去除搜索树当中不必要的搜索路径，从而优化算法，降低时间开销。
常见的剪枝包括：
1可行性剪枝 2排除等效剪枝 3最优性剪枝 4顺序剪枝 5记忆化剪枝
下面将一一举例介绍其原理：
1可行性剪枝
在寻找所有的解决方案时，若某种方案明显不可行/无法找到答案，则停止继续搜索。
2排除等效剪枝
当该方案和之前搜过的方案对结果具有相同效果时，可以只使用一个继续向下搜索。
3最优性剪枝
当前的方案与已有方案相比，结果明显不是最优的时候，例如在某一层取max/min后，发现不能得到更优解时，停止继续搜索。
4顺序剪枝
似乎不太常见，在搜索之前进行排序（预处理），搜索过程中可以结合其他方法进行剪枝。
5记忆化剪枝
当每个状态的结果是唯一确定且有可能会多次重复搜索时，记录每个状态的搜索结果，并在再次调用时直接返回记录值。
下面将是一些例题:
洛谷 P1731 生日蛋糕
从下往上搜索，枚举每层的半径和高度作为分支
搜索状态：第dep层，当前外表面积s,当前体积v,dep+1层的高度和半径
整个蛋糕的底面积=最底层的圆面积，这样在m-1层搜索时，只需要计算侧面积
剪枝：
1.是否可行剪枝
首先枚举，其次枚举
2.优化搜索顺序
倒序搜索枚举
3.可行性剪枝
预处理最小体积和侧面积，然后剪枝
可行剪枝
#include <bits/stdc++.h>
using namespace std;
int n,m;
int ans=2e9;
void dfs(int dep,int s,int v,int past_r,int past_h)
{
if(s >= ans) return;
if(dep == m+1 && v == n)
{
ans = min(ans,s);
return;
}
if(v >= n) return;
int rest_dep = m - dep + 1;
if(rest_dep * past_r * past_r * past_h + v < n) return;
if(dep == 1)
{
for(int r = past_r; r >= m; --r)
for(int h = m; h <= past_h; ++h)
dfs(dep + 1,s + r * r + 2 * r * h,v + r * r * h,r,h);
}
else
{
for(int r=past_r-1; r>=m-dep+1; --r)
for(int h=m-dep+1; h<past_h; ++h)
dfs(dep + 1,s + 2 * r * h,v + r * r * h,r,h);
}
}
int main()
{
scanf("%d%d",&n,&m);
dfs(1,0,0,28,28);
if(ans == 2e9) printf("0\n");
else printf("%d\n",ans);
}
洛谷 P1120 小木棍
剪枝
1.优化搜索顺序：从大到小排序，优先尝试长的木棍
2.排除等效分支：
(1).因为先拼一根a长度的，再拼一根b长度的等于先拼一根b长度的，再拼一根a长度,只要搜索其中一种
(2).记录最近一次尝试拼接的木棍长度，如果搜索失败则不尝试同种长度的木棍
(3).当尝试拼入的第一根木棍就返回失败，则直接回溯
(4).如果当前木棍拼入后，一节木棒被填充完整，而另一根木棍
失败了，则直接回溯
剪枝代码
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n,sum=0,a[MAXN];
bool vis[MAXN];
int cmp(int a,int b)
{
return a>b;
}
bool dfs(int num,int len,int now_len,int number)
{
if(number==sum/len)return 1;
if(now_len==len)
{
if(dfs(1,len,0,number+1))return 1;
}
for(int i=num; i<=n; i++)
{
if(!vis[i]&&now_len+a[i]<=len)
{
vis[i]=true;
if(dfs(i+1,len,now_len+a[i],number))return 1;
vis[i]=false;
if(a[i]==len-now_len||now_len==0)break;
while(a[i]==a[i+1])i++;
}
}
return 0;
}
int main()
{
memset(vis,false,sizeof(vis));
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
sort(a+1,a+1+n,cmp);
for(int i=a[1]; i<=sum; i++)
{
if(sum%i!=0)continue;
if(dfs(1,i,0,0))
{
cout<<i<<endl;
break;
}
}
}