最近做搜索里面的题目，发现还是有很多漏洞的
比如下面这道小猫爬山题，还是不会做看的答案...气死我了
小猫爬山
时间限制: 1.000 Sec 内存限制: 128 MB
提交 状态
题目描述
Freda和rainbow饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN。当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？
输入
第一行包含两个用空格隔开的整数，N和W。
接下来N行每行一个整数，其中第i+1行的整数表示第i只小猫的重量Ci。
输出
输出一个整数，最少需要多少美元，也就是最少需要多少辆缆车。
样例输入 Copy
5 1996 1 2 1994 12 29
样例输出 Copy
2
提示
对于100%的数据，1<=N<=18，1<=Ci<=W<=10^8。
思路：一开始其实我最先想到的是贪心，但仔细想想证明不出来最优方案。一开始想着用双指针，拿一个大猫，再拿很多小猫和它搭配一起放，但都不对。这时我们注意到，猫的数量很少，换句话就是最多用的缆车就是18个。那我们考虑dfs。
可以把缆车考虑成一个个空格，要在空格里面填数字。那就每次循环空格，看哪个空格能填下当前的小猫。
注意这题是要优化的。两个优化：1.当前答案大于之前答案，立即return。2.将小猫排序，先安排大的小猫，这样如果大猫不行就直接跳，省的放了小猫后发现不行还要一步步回去。
代码附上：
#include<iostream>
#include<algorithm>
using namespace std;
int n,w,ans=100;
int c[100],car[100];
bool sorrt(int i,int j){
return i>j;
}
void dfs(int cat_num,int car_num){
// cout<<cat_num<<" "<<car_num<<" "<<car[car_num]<<endl;
if(car_num>ans){
return ;
}
if(cat_num>n){
ans=car_num;
return ;
}
for(int i=0;i<car_num;i++){
if(c[cat_num]+car[i]<=w){
car[i]+=c[cat_num];
dfs(cat_num+1,car_num);
car[i]-=c[cat_num];
}
}
car[car_num]=c[cat_num];
dfs(cat_num+1,car_num+1);
}
int main()
{
cin>>n>>w;
for(int i=1;i<=n;i++){
cin>>c[i];
}
sort(c+1,c+n+1,sorrt);
dfs(1,1);
cout<<ans;
return 0;
}