莫欺少年穷，修魔之旅在这开始—>算法提高课题解

剪枝与优化

1. 优化搜索顺序
2. 排除等效冗余
3. 可行性剪枝
4. 最优性剪枝
5. 记忆化搜索（dp）

思路：

1. 选择优化搜索顺序，可行性剪枝，最优性剪枝
2. 枚举所有小车，如果看小猫要坐哪个小车，出来后要恢复现场
3. 已有的小车小猫都不坐，偏要开一个组，这就不需要恢复现场了

#include<bits/stdc++.h>

using namespace std;

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

void dfs(int u,int k)
{
    //最优性剪枝
    if(k>=ans) return;

    //小猫全部入座
    if(u==n) ans=k;

    //枚举所有小车
    for(int i=0;i<k;i++)

        //可行性剪枝
        if(sum[i]+w[u]<=m)
        {
            sum[i]+=w[u];
            dfs(u+1,k);

            //恢复现场
            sum[i]-=w[u];
        }

    //开一个新组
    sum[k]=w[u];
    dfs(u+1,k+1);
}

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;
}