[AcWing 165] 小猫爬山

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 50 + 10;

int n, m;
int w[N];
int sum[N]; // 每组的重量之和
int ans = 1e9;

// 当前枚举到w[u] 分了k组
void dfs(int u, int k)
{
    // 递归边界 和 最优性剪枝
    if (u == n || k >= ans) {
        ans = min(ans, k);
        return;
    }
    // 放到现有的组中
    for (int i = 0; i < k; i ++)
        // 可行性剪枝
        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;
}

void solve()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
        cin >> w[i];
    sort(w, w + n, greater<int>());
    dfs(0, 0);
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}