codevs 4228 小猫爬山 【搜索】By cellur925

题目描述 Description

Freda和rainbow饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN。当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？

日常刷lyd书系列。qwq。

个人觉得是一道不错的搜索入门题（没错我学搜索近九个月仍处于入门阶段qwq）。

先总结一下，（目前）感觉搜索有两种：求最值/求方案数。

前者如本题，搜索时分两种情况，保持当前的最优解，迫不得已向下开。每次搜索结束子状态后，还原子状态原状。

dfs函数传的参数是什么？当前需要的状态。在本题中，我们关心的就是已经运送的小猫数，用的缆车数量，各缆车目前载重量。最后者，我们可以用数组来记录。搜索边界是当在运送的小猫now==n+1.

两个小剪枝：先按小猫重量从大往小排序，优先搜索更大的小猫；因为我们dfs的过程实际在不断更新最优解，所以当现在搜出来的结果大于等于可行解就可以停止搜索了，因为它一定不会成为更优解。

code

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 int n,limit;

 int w[];

 int ans,pos[];

 bool cmp(int a,int b)

 {

     return a>b;

 }

 void dfs(int now,int cnt)

 {

     if(cnt>=ans) return ;

     if(now==n+)

     {

         ans=min(ans,cnt);

         return ;

     }

     for(int i=;i<=cnt;i++)

      if(pos[i]+w[now]<=limit)

      {

           pos[i]+=w[now];

           dfs(now+,cnt);

           pos[i]-=w[now];

      }

     pos[cnt+]=w[now];

     dfs(now+,cnt+);

     pos[cnt+]=;

 }

 int main()

 {

     scanf("%d%d",&n,&limit); ans=n;

     for(int i=;i<=n;i++) scanf("%d",&w[i]);

     sort(w+,w++n,cmp);

 //    for(int i=1;i<=n;i++) printf("%d ",w[i]);

 //    printf("\n");

     dfs(,);

     printf("%d",ans);

     return ;

 }