算法刷题-小猫爬山

本题来源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;  //没有这个会Tif(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只猫开始搜，当前使用的车的数量是0cout<<ans<<endl;return 0;
}

总结一下这类将n个物品放入有限制的容器中，并且求最小容器数的解法：

枚举这n个物品，枚举到第i个物品时，先给第i个物品选择要放入的地方（这个地方可以是已经有的，也可以是新建的。然后再去枚举下一个物品。）。在这其中，如何来“标记”已经选好的地方呢？可以将“已经使用的数量”作为参数，放入DFS的参数中。