• 我们遍历依次遍历每只小猫，除了第一只小猫（只能新开一辆缆车），其他小猫可以有多种选择，放在有猫的某个缆车中 或者 新租一个缆车放这个小猫

• 考虑如何剪枝：

（1）优化搜索顺序：我们应该按照小猫重量从大到小排序遍历小猫，这样分支比较少。

（2）排除等效冗余：无

（3）可行性剪枝：如果某只小猫放置在某个缆车中会超过缆车的最大容量，则应该直接回溯。

（4）最优性剪枝：如果当前搜索方案需要的缆车数量大于当前最优解，则应该直接回溯。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n, m;
int w[N];  // 小猫重量
int sum[N];  // 缆车被占用的重量
int ans = N;

// u: 当前遍历到的小猫; k: 目前需要的缆车数量
void dfs(int u, int k) {

    // (4) 最优性剪枝
    if (k >= ans) return;
    if (u == n) {
        ans = k;
        return;
    }

    for (int i = 0; i < k; i++)
        if (sum[i] + w[u] <= m) {  // (3) 可行性剪枝
            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];

    // (1) 优化搜索顺序
    sort(w, w + 5, greater<int>());

    dfs(0, 0);

    cout << ans << endl;

    return 0;
}