穿越隧道

搜索：
1.优化搜索顺序
大部分情况下，应优选搜索分支较少的节点
2.排除等效冗余
3.可行性剪枝
4.最优性剪枝
5.记忆化搜索（DP)
在这题中
1.优化搜索顺序：√（有）
猫越重，分支可能越少。
对猫的重量从大到小排序
2.排序等效冗余 ：×（无重复性情况）
3.可行性剪枝：√（有）
如果某辆车猫的重量超出了W(剪枝）
4.最优化剪枝：√（有）
如果新开车的数量已经大于ans，就直接退出
5.记忆化搜搜（DP)：×（无）

#include <bits/stdc++.h>
using namespace std;
const int N = 20;int n,m;
int w[N];//每只猫的重量
int sum[N];//每辆车的重量
int ans = N;//最坏情况，每辆车一只猫
void dfs(int u, int k){//最优性剪枝 if(k >= ans){//当前车的数量，大于等于最坏情况时 return ; }if(u == n){//递归出口 ans = k;return ;}for(int i = 0; i < k; i++){//第u只猫，能放到k辆车的哪辆车上去。if(sum[i] + w[u] <= m){//可行性剪枝 sum[i] += w[u];dfs(u + 1, k);sum[i] -= w[u];//恢复现场 } }sum[k] = w[u];//新开一辆车dfs(u + 1,k + 1);sum[k] = 0;//恢复现场 
} 
int main(){cin >> n >> m;for(int i = 0; i < n; i++) cin >> w[i];sort(w,w + n);reverse(w,w + n);//从大到小 dfs(0,0);/*第一个0：当前搜到第0只猫第二个0：当前车的数量为0*/ cout << ans << endl;return 0; 
}