AcWing 165. 小猫爬山(详细注释版本)
原题链接
简单
作者:
__葑茚丶誋憶
,
2024-04-05 15:32:38
,
所有人可见
,
阅读 3
//把猫的重量从大到小排序 这样搜索的时候分支更少 会减少很多状态
//对于每只猫有两种选择 加入到已有的车里面去 或者开一俩新的车 穷举这两种方案即可
#include<iostream>
#include<algorithm>
using namespace std;
const int N=20;
int cat[N],sum[N];//sum表示当前这辆车的重量
int n,w,res=1e8;
void dfs(int u,int k)//u表示第几只猫 k表示当前共有几辆车
{
if(k>=res) return ;//如果当前车的数量已经超过了之前的最优解,说明之前的肯定更好,直接返回
if(u==n)//所有小猫都已经安排好
{
res=k;//k肯定比res要小,因为大于的情况已经被剪枝了
return ;
}
//第一种情况 把猫放到已经有的车里去
for(int i=0;i<k;i++)//遍历每一辆车,看看能不能放的下
{
if(sum[i]+cat[u]<=w)
{
sum[i]+=cat[u];
dfs(u+1,k);//递归下一只猫 因为没有新增加车,所以车的数量不变
sum[i]-=cat[u];//回溯
}
}
//第二种情况 把猫放到新的一辆车上去
sum[k]=cat[u];//因为车的下标从0开始,i<k,所以k就是最新一辆车的下标
dfs(u+1,k+1);
sum[k]=0;
}
int main()
{
cin>>n>>w;
for(int i=0;i<n;i++)
cin>>cat[i];
sort(cat,cat+n);
reverse(cat,cat+n);
dfs(0,0);//当前有0辆车
cout<<res<<endl;
return 0;
}