剪枝与优化的方法
1.优化搜索顺序
大部分情况下，我们应该优先搜索分支较少的节点
2.排除等效冗余
3.可行性剪枝
4.最优性剪枝
5.记忆化搜索（DP）
1.小猫爬山
1.优化搜索顺序-》从大到小排序进行搜索
2.可行性剪枝-》假如该组总和+当前数则不可行
3.最优性剪枝-》因为要答案最小，假如搜索过程中已经大于我的答案了，说明后面的搜索都没用
#include<bits/stdc++.h> using namespace std; const int N=20; int n,W; int w[N],ans=N; int group[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(group[i]+w[u]<=W)//可行性剪枝 { group[i]+=w[u];//该组加上他 dfs(u+1,k);//继续处理下一个数，组数不变 group[i]-=w[u];//恢复现场 } //新开一个组 group[k]+=w[u];//该组加上他 dfs(u+1,k+1);//继续处理下一组，组数加一 group[k]-=w[u];//恢复现场 } int main() { cin>>n>>W; for(int i=0;i<n;i++) cin>>w[i]; //下面两步是优化搜索顺序 sort(w,w+n); //从大到小排序 reverse(w,w+n); dfs(0,0); cout<<ans<<endl; return 0; }
2.数独
1.优化搜索顺序->选择分支较少的点
2.可行性剪枝-》不能与行、列和九宫格重复
3.最优性剪枝-》位运算优化，用来判断那个位置能填的数有哪些
#include<bits/stdc++.h> using namespace std; const int N=9,M=1<<N; int ones[M],mark[M]; char str[100]; int row[N],col[N],cell[3][3]; void init()//赋予状态 { //一开始所有行列九宫格都没数字 for(int i=0;i<N;i++) col[i]=row[i]=M-1; for(int i=0;i<3;i++) for(int j=0;j<3;j++) cell[i][j]=M-1; } void draw(int x,int y,int t,bool is_set)//用于在str上画数字 { if(is_set) str[x*N+y]='1'+t;//假如是要画数字的，则在str上赋值 else str[x*N+y]='.';//反之是空位的 int v=1<<t;//用来获取该数字的二进制 if(!is_set) v=-v;//假如是空位，则为-v //-=v说明数字t在行和列和九宫格都用过了 row[x]-=v; col[y]-=v; cell[x/3][y/3]-=v; } int get(int x,int y)//用来获取行和列和九宫格没出现过的数 { return row[x]&col[y]&cell[x/3][y/3]; } int lowbit(int x)//用来获取某个数字第一个1 { return x&-x; } bool dfs(int cnt) { if(!cnt) return true;//假如已经弄完了 int minv=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]<minv) { minv=ones[state]; x=i,y=j; } } int state=get(x,y);//这个状态是所有空格中能填的数字的最少 for(int i=state;i;i-=lowbit(i))//开始填这个状态能填的数 { int t=mark[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++) mark[1<<i]=i;//用来算2的n次方 for(int i=0;i<1<<N;i++)//用来求某个数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);//在str上标记一下 } else cnt++;//反之是要填的数 dfs(cnt);//dfs一遍要填的所有数 puts(str);//输出填完后的str } return 0; }
3.木棒
剪枝1.最优性剪枝-》只有当长度能被总和整除时才合法
剪枝2.优化搜索顺序-》从大到小枚举
剪枝3.排除等效元素
3-1 按照组合的方式枚举
3-2 假如目前的木棍加到当前组失败了，则直接略过后面长度相等的木棍
3-3 假如木棍第一根就失败了，则一定会失败
3-4 假如木棍最后一根失败了，则一定会失败
#include<bits/stdc++.h> using namespace std; const int N=70; int n,len,sum; int w[N]; bool st[N]; bool dfs(int u,int s,int start)//u表示有第几组，s表示该组的总和，start表示从第几个开始搜 { if(u*len==sum) return true;//假如组数乘长度已经等于总和了，说明这种长度符合 if(s==len) return dfs(u+1,0,0);//假如该组已经满了，则新开一组继续搜 //剪枝3-1，i从start开始 for(int i=start;i<n;i++) { if(st[i]) continue;//假如用过 if(s+w[i]>len) 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]==len) 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) { memset(st,0,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); len=w[0]; //最大一组就是自己sum while(1) { //剪枝1 if(sum%len==0&&dfs(0,0,0))//假如这个长度符合 { cout<<len<<endl; break; } len++; if(len>sum) break;//假如已经超了 } } return 0; }
4.生日蛋糕
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=25,INF=1e9; int n,m; int minv[N],mins[N]; int R[N],H[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--)//枚举合法的r for(int h=min(H[u+1]-1,(n-v)/r/r);h>=u;h--)//枚举合法的h { int t=0; if(u==m) t=r*r;//表面积的增加量 R[u]=r,H[u]=h;//该点的r是r，h是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; } R[m+1]=H[m+1]=INF; dfs(m,0,0);//从底往上搜索 if(ans!=INF) cout<<ans<<endl;//假如有方案 else cout<<0<<endl;//假如没方案输出0 return 0; }
