两个地方可以剪枝 1.将猫的重量从大到小排序 2.如果方案比现有方案需要的车的数量多就直接放弃

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
//猫的重量 每辆车现在的重量
int cat[N], sum[N];
int ans = N;
int m, n;

// 猫、车
void dfs(int u, int k)
{
    if(k >= ans) return;

    if(u == n)
    {
        ans = k;
        return;
    }

    for(int i = 0; i < k; i++)
    {
        if(cat[u] + sum[i] <= m)
        {
            sum[i] += cat[u];
            dfs(u + 1, k);
            sum[i] -= cat[u];
        }
    }

    sum[k] = cat[u];
    dfs(u + 1, k + 1);
    sum[k] = 0;
}


int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        cin >> cat[i];

    //先考虑体重大的猫，选择比较少
    sort(cat, cat + n);
    reverse(cat, cat + n);

    dfs(0, 0);

    cout << ans << endl;

    return 0;
}