P3052 [USACO12MAR]Cows in a Skyscraper G

做题 OJ

题意
给出n个物品，体积为w[i]，现把其分成若干组，要求每组总体积<=W，问最小分组。(n<=18)

解法
dfs+小剪枝
1，如果当前的答案超过ans 显然不合理 剪掉
2，我们可以从大到小选择每一个放在那一个电梯中 缩小枚举空间 (从小到大枚举的空间更多 耗时更长)

代码

#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;
}