题解 P3052 【[USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper】
流逝丶
2019-11-04 14:10:14
我不会退火也不会状压DP，但也能过这个题
看一眼数据范围$n\le18$,这题可以爆搜
不过加个优化，给原序列排个序，从大到小排，依次枚
举当前物品在哪个组，或者给它另开一个组，加上最优
性剪枝，妥妥的能过
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,w,ans;
int a[20],b[20];
bool cmp(const int &a,const int &b){
return a>b;
}
void dfs(int now,int tot){
if(tot>=ans)return ;
if(now==n+1){
ans=min(tot,ans);
return ;
}
for(int i=1;i<=tot;++i)
if(b[i]+a[now]<=w){
b[i]+=a[now];
dfs(now+1,tot);
b[i]-=a[now];
}
b[tot+1]=a[now];
dfs(now+1,tot+1);
b[tot+1]=0;
}
int main(){
scanf("%d%d",&n,&w);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
sort(a+1,a+1+n,cmp);
ans=n;
dfs(1,0);
printf("%d",ans);
return 0;
}
```