dfs

数据量很小，可以考虑暴搜，那我们考虑以怎样的顺序去搜索，假如每一趟用一个桶，那么就是最小需要几个桶的问题。我们可以考虑当前的衣服，1.可以放进已有的桶，2.在添加一个桶。如果不进行优化会超时的，对于第二种情况，每一个衣服都可以创建一个新桶，没有优化的余地了。对于第一种情况，我们知道搜索一般都是树形结构，如果扩展的结点越少，那么搜索的范围也就越小，显然，越大的衣服重量，后续的分枝就越小，毕竟越小的选择越大，那么分枝就越大，所以我们需要将衣服重量从大到小排序。还有一个常规的优化就是，如果当前的桶数已经大于等于目前的一个最优解，直接返回即可。

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn=30;
int a[maxn];
int sum[maxn];
int n,m;
int ans=maxn;
void dfs(int u,int k)//u当前遍历到第几只猫，k已经用了几个桶
{
    if(k>=ans)//如果目前用的桶已经超过当下的最优解，已经没有必要搜索下去了
        return;
    if(u==n)
    {
        ans=k;//不用是ans=min(ans,k)，因为前面k>=ans,已经返回了
        return;
    }
    for(int i=0;i<k;i++)
    {
        if(a[u]+sum[i]<=m)//如果在第i个放下第u件衣服没有超过m，可以继续遍历下去
        {
            sum[i]+=a[u];
            dfs(u+1,k);
            sum[i]-=a[u];//回溯
        }
    }
    sum[k]=a[u];//新建一个桶
    dfs(u+1,k+1);
    sum[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;
}