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