代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
int n, m, ans = N;
//w[i]表示第i只小猫的重量
//sum[i]表示第i个缆车的重量
int w[N], sum[N];

//t表示当前搜索到的小猫
//k表示目前已经安排的缆车数量
void dfs(int t, int k)
{
    //最优性剪枝
    if(k >= ans) return;

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

    //将当前的小猫安排在已有缆车中
    for(int i = 0; i < k; i++)
    {
        //如果当前小猫的重量 + 缆车i的重量 超过了 缆车的承重
        //可行性剪枝
        if(w[t] + sum[i] <= m)
        {
            sum[i] += w[t];
            dfs(t + 1, k);
            sum[i] -= w[t];
        }
    }

    //将当前的小猫安排在新缆车中
    //注意：k的编号是从0开始的，所以这里将小猫安排在新缆车k中
    sum[k] = w[t];
    dfs(t + 1, k + 1);
    //恢复现场
    sum[k] = 0;
}

int main()
{
    cin >> n >> m;

    for(int i = 0; i < n; i++) cin >> w[i];

    //按小猫体重从大到小排序
    //优化搜索顺序，优先搜索分支较少的结点
    sort(w, w + n);
    reverse(w, w + n);

    dfs(0, 0);

    cout << ans << endl;

    return 0;
}

核心

搜索与回溯