nc51012 小猫爬山

有n只猫，重量分别为C[i]，要将所有小猫都放进缆车里，缆车的最大承重为W，问至少要多少辆缆车才能装下？
1<=n<=18; 1<=C[i]<=W<=1e8

n比较小，可以暴力搜索，dfs(x,g)表示当前已经分了g个组，考虑如何分配第x只猫，枚举将猫放进g组中的每一个，另外也可以让它单独一组。按体重从大到小排序，可以触发剪枝而大大提高效率。

#include <bits/stdc++.h>
using namespace std;
int n, W, C[20], T[20], ans;
void dfs(int x, int g) {
    if (g >= ans) {
        return;
    }
    if (x > n) {
        ans = min(ans, g);
        return;
    }
    for (int i = 1; i <= g; i++) {
        if (T[i]+C[x] <= W) {
            T[i] += C[x];
            dfs(x+1, g);
            T[i] -= C[x];
        }
    }
    T[g+1] += C[x];
    dfs(x+1, g+1);
    T[g+1] -= C[x];
}
int main() {
    cin >> n >> W;
    for (int i = 1; i <= n; i++) {
        cin >> C[i];
    }
    sort(C+1, C+1+n, [&](int x, int y) {
        return x > y;
    });
    ans = 100;
    dfs(1, 0);
    cout << ans << "\n";
    return 0;
}