2021.11.10/dfs/小猫爬山
https://www.acwing.com/problem/content/167/
有y总视频讲解

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, w, ans = 20;
ll a[20], st[20], b[20];

void dfs(int u, int idx){
    if(idx >= ans) return;
    if(u == n){
        ans = min(ans, idx);
        return ;
    }
    for(int i = 0; i <= idx; i++){
        if(b[i] + a[u] <= w) b[i] += a[u], dfs(u + 1, idx), b[i] -= a[u];
    }
    if(b[idx] != 0)
        b[idx + 1] += a[u], dfs(u + 1, idx + 1), b[idx + 1] -= a[u];
    return ;
}

int main(){
    cin >> n >> w;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n, [](const int& x, const int& y){return x > y;});
    dfs(0, 0);
    cout << ans + 1;
    return 0;
}