P3052 [USACO12MAR]Cows in a Skyscraper G

Problem. OJ

The question
give n Items , The volume is w[i], Now they are divided into several groups , The total volume of each group is required <=W, Minimum grouping .(n<=18)

solution
dfs+ Pruning
1, If the current answer exceeds ans It's obviously unreasonable cut off
2, We can choose which one to put in the elevator from big to small Reduce enumeration space ( There is more space to enumerate from small to large Takes longer )

Code

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 22; 
int p[N];
int g[N];
int n,m,ans; 
void dfs(int k,int t){
    
	if(t>ans) return;
	if(k<1){
    
		ans=min(ans,t);return;
	}
	for(int i=0;i<t;i++){
    
		if(g[k]+p[i]>m) continue;
		p[i]+=g[k];
		dfs(k-1,t);
		p[i]-=g[k]; 
	}
	p[t]=g[k];
	dfs(k-1,t+1);
	p[t]=0;
}
signed main(){
    
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>g[i];
	sort(g+1,g+1+n);
	ans = N*N;
	dfs(n,1);
	cout<<ans<<endl;
	return 0;
}