小猫爬山

排序，然后递归。。。剩下的放注释里了: )

蒟蒻写法：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 20;
int n, w, sum[N], c[N], ans = N;

bool cmp(int a, int b) {
    return a > b;
}

void dfs(int pos, int k) {
    if (k >= ans) return; // 最优性剪枝
    if (pos == n) {
        ans = k; // also written as ans = k + 1 - 1; 因为车从0到k-1,有k辆
        return;
    }
    for (int i = 0; i < k; i++) { // 已有车编号0~k-1
        if (c[pos] + sum[i] <= w) { // 可行性剪枝：当前猫和已有质量小于车能承载的质量
            sum[i] += c[pos];
            dfs(pos + 1, k);
            sum[i] -= c[pos]; // 恢复现场
        }
    }
    sum[k] += c[pos]; // 先放车，再开新车，不是if,else的关系
    dfs(pos + 1, k + 1);
    sum[k] = 0; // also written as sum[k] -= c[pos];
}

int main() {
    cin >> n >> w;
    for (int i = 0; i < n; i++) cin >> c[i];
    sort(c, c + n, cmp); // 优化搜索顺序
    /*also written as
    sort(c, c + n);
    dfs(0, 0);*/
    dfs(0, 0); // 当前猫的编号，当前新车的编号
    cout << ans << endl;
    return 0;
}