Methods of pruning and optimization
1. Optimize the search order
In most cases, we should give priority to searching nodes with fewer branches
2. Exclude Equivalent Redundancy
3. Feasibility pruning
4. Optimal pruning
5. Memory search (DP)
1. The kitten climbs the mountain
Title
https://www.acwing.com/problem/content/description/167/
1. Optimize the search order – “Sort from big to small to search
2. Feasibility pruning-“If the sum of the group + the current number is not feasible
3. Optimal pruning-“Because the answer is the smallest, if it is already greater than my answer during the search process, it means that the subsequent search is useless
#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 is the number, k is how many groups
{
if(k>=ans) return;//optimal pruning
if(u==n)//If all points are searched
{
ans=k;
return;
}
for(int i=0;i<k;i + + )
if(group[i] + w[u]<=W)//feasibility pruning
{
group[i] + =w[u];//Add him to this group
dfs(u + 1,k);//Continue to process the next number, the number of groups remains unchanged
group[i]-=w[u];//restore scene
}
// open a new group
group[k] + =w[u];//The group plus him
dfs(u + 1,k + 1);//Continue to process the next group, add one to the number of groups
group[k]-=w[u];//restore scene
}
int main()
{
cin>>n>>W;
for(int i=0;i<n;i + + ) cin>>w[i];
//The next two steps are to optimize the search order
sort(w,w + n);
//Sort from largest to smallest
reverse(w,w + n);
dfs(0,0);
cout<<ans<<endl;
return 0;
}
2. Sudoku
Titlehttps://www.acwing.com/problem/content/description/168/
1. Optimize the search order -> select points with fewer branches
2. Feasibility pruning-” cannot be repeated with row, column and Jiugongge
3. Optimal pruning-“Bit operation optimization, used to judge what numbers can be filled in that position
#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()//given state
{
//In the beginning, all rows, columns and nine squares have no numbers
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)//used to draw numbers on str
{
if(is_set) str[x*N + y]='1' + t;//If you want to draw numbers, then assign a value on str
else str[x*N + y]='.';//Conversely, it is empty
int v=1<<t;//Used to get the binary of the number
if(!is_set) v=-v;//If it is empty, it is -v
//-=v indicates that the number t has been used in rows and columns and Jiugongge
row[x]-=v;
col[y]-=v;
cell[x/3][y/3]-=v;
}
int get(int x, int y)//Used to get rows and columns and numbers that have not appeared in Jiugongge
{
return row[x] &col[y] &cell[x/3][y/3];
}
int lowbit(int x)//Used to get the first 1 of a certain number
{
return x &-x;
}
bool dfs(int cnt)
{
if(!cnt) return true;//If it has been done
int minv=10;
int x,y;
for(int i=0;i<N;i ++ )//Find the smallest number used in an unfilled position
for(int j=0;j<N;j++)
if(str[i*N + j]=='.')//If it is to fill in mathematics
{
int state=get(i,j);//Get the number that can be filled in this position
if(ones[state]<minv)
{
minv=ones[state];
x=i,y=j;
}
}
int state=get(x,y);//This state is the least number that can be filled in all blanks
for(int i=state;i;i-=lowbit(i))//Start to fill in the number that can be filled in this state
{
int t=mark[lowbit(i)];//Get what the number is
draw(x,y,t,true);//fill in the number
if(dfs(cnt-1)) return true;
draw(x,y,t,false);//restore scene
}
return false;
}
int main()
{
//initialization
for(int i=0;i<N;i ++ ) mark[1<<i]=i;//used to calculate the nth power of 2
for(int i=0;i<1<<N;i ++ )//used to find the number of a certain number i
for(int j=0;j<N;j++)
ones[i] + =i>>j &1;
while(cin>>str,str[0]!='e')
{
init();//Re-assign the state
int cnt=0;
for(int i=0,k=0;i<N;i ++ )
for(int j=0;j<N;j ++ ,k ++ )
if(str[k]!='.')//If a certain position is mathematics
{
int t=str[k]-'1';//Convert to a number
draw(i,j,t,true);//mark on str
}
else cnt + + ;//Conversely, the number to be filled
dfs(cnt);//all the numbers to be filled in dfs
puts(str);//Output filled str
}
return 0;
}
3. Wooden stick
Title
https://www.acwing.com/problem/content/169/
Pruning 1. Optimal pruning – “only valid when the length is divisible by the sum
Pruning 2. Optimize the search order – “enumerate from big to small
Pruning 3. Excluding equivalent elements
3-1 Enumerate by combination
3-2 If the current wooden stick fails to be added to the current group, skip the subsequent wooden sticks of equal length
3-3 If the first stick fails, it will definitely fail
3-4 If the last stick fails, it must fail
#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 indicates which group, s indicates the sum of the group, and start indicates which number to start searching
{
if(u*len==sum) return true;//If the number of groups multiplied by the length is already equal to the sum, it means that the length meets the
if(s==len) return dfs(u + 1,0,0);//If the group is already full, open a new group and continue searching
//Pruning 3-1, i starts from start
for(int i=start;i<n;i++)
{
if(st[i]) continue;//If used
if(s + w[i]>len) continue;//feasibility pruning
st[i]=true;//mark used
if(dfs(u,s + w[i],i + 1)) return true;//Put it into this group and continue searching
st[i]=false;//backtracking, restore the scene
//pruning 3-3
if(!s) return false;
//pruning 3-4
if(s + w[i]==len) return false;
//pruning 3-2
int j=i;
while(j<n & amp; & amp;w[j]==w[i]) j + + ;
i=j-1;
}
return false;//Conversely does not meet
}
int main()
{
while(cin>>n,n)
{
memset(st,0,sizeof st);//Clear the previous state
sum=0;
for(int i=0;i<n;i + + ) cin>>w[i], sum + =w[i];
//Pruning 2, optimize the search order
sort(w,w + n);
reverse(w,w + n);
len=w[0];
//The largest group is your own sum
while(1)
{
//pruning 1
if(sum%len==0 & amp; & amp;dfs(0,0,0))//If this length meets
{
cout<<len<<endl;
break;
}
len + + ;
if(len>sum) break;//If it has exceeded
}
}
return 0;
}
4. Birthday cake
Titlehttp://ybt.ssoier.cn:8088/problem_show.php?pid=1441
#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 the volume is already greater than the maximum volume
if(s + mins[u]>=ans) return;//If it is greater than or equal to the current answer, it is meaningless to do it later
if(s + 2*(n-v)/R[u + 1]>=ans) return;//reasoning optimization
if(!u)//If the last number is found
{
if(v==n) ans=s;//If the volume just matches, then update the minimum value
return;
}
for(int r=min(R[u + 1]-1,(int)sqrt(n-v));r>=u;r--)//enumerate legal r
for(int h=min(H[u + 1]-1,(n-v)/r/r);h>=u;h--)//enumerate legal h
{
int t=0;
if(u==m) t=r*r;//Increase of surface area
R[u]=r, H[u]=h;//The point r is r, h is h
dfs(u-1,v + r*r*h,s + 2*r*h + t);//Process the next step
}
}
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);//Search from bottom to top
if(ans!=INF) cout<<ans<<endl;//If there is a plan
else cout<<0<<endl;//If there is no plan, output 0
return 0;
}
The knowledge points of the article match the official knowledge files, and you can further learn relevant knowledge algorithm skill treehomepage overview 47437 people are learning