dfs思路

每次小猫有两种选择:一是新开一辆车, 二是将它放入已经存在的车中;
每次深搜完需要恢复现场

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20;
int a[N];
int s[N];
int n, m, ans = 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(s[i] + a[u] <= m)
        {
            s[i] += a[u];
            dfs(u + 1, k);
            s[i] -= a[u];
        }
    }
    //第一种安排,新开一辆车
    s[k] = a[u];
    dfs(u + 1, k + 1);
    s[k] = 0;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    //为了提高效率,将小猫重量按从大到小排序更容易剪枝!
    sort(a, a + n);
    reverse(a, a + n);
    dfs(0, 0);

    cout << ans << endl;

    return 0;
}