AcWing 165. 小猫爬山(dfs+剪枝优化)
原题链接
简单
作者:
逸误
,
2024-04-07 20:47:52
,
所有人可见
,
阅读 5
//剪枝笔记:优先考虑决策少的元素,让dfs搜索树上面的层次少一些结点,剪枝可以剪掉更多结点
//这里以从前往后的顺序放猫,每个猫有两种选择:新开一辆缆车/进入前面有猫上过的缆车
//重量越大的猫,选择越少,因为有不少缆车放不下了
//选择少也就可以让dfs搜索树上面结点变少!所以先排好序,从重的猫开始放
//同时,dfs时小猫也应该优先放旧车,再考虑放入新车,如果先放新车,一开始就把所有车开了,每次要遍历所有的车
//这是dfs函数内两个操作之间的顺序问题!即:优化搜索顺序
//最优性剪枝:如果当前开的缆车数量>=前面算出来的最少值,直接返回,不会是最优解了
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int ans=N;//最少需要多少缆车
int n,w;
int sum[N];//每个缆车现在放了多重的猫
int cat[N];//每个猫重量
void dfs(int u,int k)//现在放到第i只猫,已经用了k辆缆车
{
if(k>=ans)
return;
if(u==n+1)//放完了,还没被前面剪枝掉
{
ans=k;//更新ans
return;
}
//接下来先放现有的缆车,再考虑加一辆缆车!
for(int i=1;i<=k;i++)
{
if(sum[i]+cat[u]>w)//放不下
continue;
sum[i]+=cat[u];//第u只猫放在第i辆缆车上
dfs(u+1,k);
sum[i]-=cat[u];//恢复现场!
}
//接下来尝试加一辆缆车
sum[k+1]=cat[u];
dfs(u+1,k+1);
sum[k+1]=0;
return;
}
int main()
{
cin>>n>>w;
for(int i=1;i<=n;i++)
cin>>cat[i];
sort(cat+1,cat+1+n);
reverse(cat+1,cat+1+n);//从大到小排序就再reverse一下
dfs(1,0);
cout<<ans<<endl;
return 0;
}