翰翰和达达饲养了N只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CNC1、C2……CN。
当然，每辆缆车上的小猫的重量之和不能超过W。
每租用一辆缆车，翰翰和达达就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？
输入格式
第1行：包含两个用空格隔开的整数，N和W。
第2..N+1行：每行一个整数，其中第i+1行的整数表示第i只小猫的重量CiCi。
输出格式
输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。
数据范围
1≤N≤181≤N≤18,
1≤Ci≤W≤1081≤Ci≤W≤108
输入样例：
5 1996
1
2
1994
12
29
输出样例：
2算法：dfs + 剪枝
题解：通过分析题目得知，这是一道搜索题，还有点贪心的感觉，搜索就不多说了，剪枝来讲一下。下面有两种情况可以减少搜索次数:第一，当当前答案大于或等于我们已知的答案，那就就直接return了；第二，我们将小猫按体重排序，根据剪枝的优先搜索顺序得知。
#include <iostream>
#include <cstdio>
#include <algorithm> using namespace std; const int maxn = 1e3+; int arr[maxn];
int sum[maxn];
int ans = 1e9+;
int n, w; bool cmp(int a, int b) {
return a > b;
} void dfs(int x, int num) {
if(ans <= num) { //剪枝1
return;
}
if(x == n + ) {
ans = min(ans, num);
return;
}
for(int i = ; i <= num; i++) { //遍历每辆缆车
if(sum[i] + arr[x] <= w) {
sum[i] += arr[x];
dfs(x + , num);
sum[i] -= arr[x];
}
}
sum[num + ] += arr[x];
dfs(x + , num + );
sum[num + ] -= arr[x];
} int main() {
ios::sync_with_stdio(false);
scanf("%d %d", &n, &w);
for(int i = ; i <= n; i++) {
scanf("%d", &arr[i]);
}
sort(arr + , arr + n + , cmp); //剪枝2
dfs(, );
printf("%d\n", ans);
return ;
}