小猫爬山

2201 小猫爬山 0x20「搜索」例题

背景

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

描述

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

输入格式

第一行包含两个用空格隔开的整数，n和w。
接下来n行每行一个整数，其中第i+1行的整数表示第i只小猫的重量ci。

输出格式

输出一个整数，最少需要多少美元，也就是最少需要多少辆缆车。

样例输入

5 1996
1
2
1994
12
29

样例输出

2

数据范围与约定

• 对于100%的数据，1<=n<=18，1<=ci<=w<=10^8。

思路：可以用深度优先搜索解决这道题，我们可以尝试把小猫分配到一辆已经租用的缆车上，或者，用另外的一辆缆车，dfs（now，cnt）现在处理第now只猫，前面的now-1

只已经分配好了，目前已经租用了cnt辆缆车。

 1.尝试把第now只小猫分配到（1-cnt ）其第i辆缆车上，如果能分配，对应的缆车cab[i]累加小猫的重量，然后递归dfs（now+1，cnt）；

2.尝试用新的缆车，也就令cab[cnt+1]=a[now],递归dfs（now+1，cnt+1）；

  这道题必须要剪枝才能过，我们搜索到cnt>=ans，在当前分枝就可以回溯了。除此之外，重量大的 猫更难运输，所以我们可以优先搜索重量较大的猫，减少搜索树的“分支”的数量；