算法刷题-小猫爬山
本题来源165. 小猫爬山 - AcWing题库
翰翰和达达饲养了 NN 只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。
当然，每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车，翰翰和达达就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N只小猫都运送下山？
输入格式
第 1 行：包含两个用空格隔开的整数，N 和 W。
第 2..N+1行：每行一个整数，其中第 i+1行的整数表示第 i 只小猫的重量 Ci。
输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。
数据范围
1≤N≤18,
1≤Ci≤W≤10^8
输入样例：
5 1996
1
2
1994
12
29
输出样例：
2我们想一下，如若使用DFS进行解答（暴力解答）。
其实许多类似的题难的地方不在于DFS本身，而在于题目的转化，即要想一种枚举的策略（或者说一种树形枚举的结构），能将所有可能性都考虑到。
首先没有任何想法的时候，不妨从问题最表面的地方出发，问题中有小猫的体重，还问我们需要的小车的数量。-->那么我们可以尝试一下从这个找到切入点，比如枚举每一个小猫，或者枚举每一个小车？
这里，我们来“试错”一下。
假如我们要枚举小猫。
我们要如何枚举呢？
那肯定是要一个一个枚举啊。
找到一个小猫后面需要干什么？（这里从开始想不好想。从结束想也不好想，那么不妨从中间开始想，但是这样的话，我们需要假设之前的已经选好了几个小车了比如{猫1，猫3}、{猫2，猫4}。现在到“猫5”了，该如何操作呢？）
假设我们已经选到“猫5”了，那么很自然，我们要从组1到组2一个一个枚举能不能装入，如果这两个组都枚举完了的话，那就要新建一个组了{猫1，猫3}、{猫2，猫4}、{猫5}。
注意，这里我们是进行了两层嵌套的枚举。
我们先不要想搜索过程中哪些可行，哪些不可行，我们先把所有的都枚举出来（搭建好这个结构再进行剪枝）
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N = 19;
int car[N];//这里存放每个车，已经有多少重量了，因为题目不要求输出方案，所以不需要单独存储每个车上有哪个具体的小猫
int cat[N];//每个小猫的重量
int n,W;
int ans = N;
void dfs(int num_cat,int counter_car){// num_cat:当前枚举到第几只猫，counter_car:已经使用几辆车了
if(counter_car>=ans) return; //没有这个会T
if(num_cat>=n){//当枚举完小猫，这一个深度（方案）完成
ans = min(ans,counter_car);//只有这个方案数小时，才更新
return ;//方案完成要返回
}
for(int i=0;i<counter_car;i++){//这里枚举到这只小猫了，就要从之前已经装车的上面依次枚举每辆车
if(car[i]+cat[num_cat]<=W){//只有小猫可以放入这辆车，才进行操作
car[i]+=cat[num_cat]; //选择的车重量加
dfs(num_cat+1,counter_car); //开始枚举下一只小猫，但是总车的数量不变
car[i]-=cat[num_cat]; //恢复现场，看一下下一辆车
}
}
car[counter_car] = cat[num_cat];//新开一个车
dfs(num_cat+1,counter_car+1);
car[counter_car]=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只猫开始搜，当前使用的车的数量是0
cout<<ans<<endl;
return 0;
}总结一下这类将n个物品放入有限制的容器中，并且求最小容器数的解法：
枚举这n个物品，枚举到第i个物品时，先给第i个物品选择要放入的地方（这个地方可以是已经有的，也可以是新建的。然后再去枚举下一个物品。）。在这其中，如何来“标记”已经选好的地方呢？可以将“已经使用的数量”作为参数，放入DFS的参数中。