dfs+sort(排序)

#include<iostream>
#include<algorithm>
using namespace std;
const int N =20;
int ans=N;
int w[N],sum[N];
int n,m;
void dfs(int u,int k)   //u代表当前这只猫，k表示车数量
{
    if(k>ans)   return ;    //如果当前车数量大于最优解即退出
    if(u==n)    //如果u为总数量，即最后一只猫后面一只，就是选完了猫时
    {
        ans=k;  //就记录ans为当前的车数量
        return;
    }
    for(int i=0;i<k;i++)    //枚举已经有的车，确定是否能在其中加入w[u]
    {
        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);   //下一只猫，下一辆车
    sum[k]-=w[u];   //恢复现场

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