小猫爬山

小猫爬山"/>

小猫爬山

画图：

三个优化，两个路径处理：
优化一：最优解剪枝=如果当前缆车数量大于了我们之前所枚举的最小缆车装载数量，则说明往后就没必要继续枚举了！
优化二：可行性剪枝=当前第u只猫的重量 + 枚举的缆车重量是大于枚举的缆车的重量。则不可放置猫咪
优化三：优化搜索顺序 = 假设一个缆车，现在有两只猫靠前排，请问先放哪只猫合适，其中的一只猫体重大，另一只体重轻。所以先放重的，因为你放了重的一下子就把缆车占满了，就不需要去枚举其余的猫是否放到这个缆车了，剪了一棵树。而放的小的猫的话，则需要往后面一直枚举考虑多种的情况。

路径处理：
当前的猫要么放在已有的缆车里，要么就新开一个缆车放！

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 20;
int n;
int cat[N], w, sum[N];  //分别表示猫的重量，缆车的承受重量，当前第i辆缆车的重量
int ans = N;//递归参数：u表示第几只猫，k表示当前缆车的数量，第二个表似乎
void dfs (int u, int k)
{if (k >= ans) return ;if (u == n){ans = k; return ;}//处理第一个分支，即枚举现有的每个缆车，看能否放入第u只猫for (int i=0; i < k;  i ++){//前提是第u只猫的重量 + 当前缆车里的重量小于wif (sum[i] + cat[u] <= w){sum[i] += cat[u];dfs (u+1, k);sum[i] -= cat[u];}}//处理第二个分支：即猫的重量+缆车重量 > w；所以新开一个缆车sum[k] = cat[u];dfs (u + 1, k + 1);sum[k] = 0;
}int main()
{cin >> n >> w;for (int i=0; i < n ; i ++)cin >> cat[i];sort (cat, cat + n, greater<int>());dfs (0, 0);cout << ans;return 0;
}