dfs就是想到一种思路枚举所有情况，注意画状态搜索树

#include <iostream>
#include <cstring>
#include <algorithm>

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;
    //当搜完所有猫，已经搜到第n+1只猫，说明搜完了n只猫
    if(u==n+1)
    {
        ans=k;
        return;
    }
    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];
        }
    }
    //上面枚举的是0到k-1号车，现在枚举新开一辆车
    sum[k]=w[u];
    dfs(u+1,k+1);
    //恢复现场
    sum[k]=0;

}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    //优化搜索顺序，先搜重的猫
    sort(w+1,w+1+n);
    reverse(w+1,w+1+n);
    //从第1号猫，车的数量为0开始搜
    dfs(1,0);
    cout<<ans;

    return 0;
}

二刷，注意剪枝

每次当前方案已经大于最优方案时，剪枝
从第一只猫。第0辆车开始搜（车的编号从0开始，猫从1开始

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=20;
//sum[i]第i辆车乘了多重的小猫
int sum[N];
int n,m;
int cat[N];
int res=N;

//第k只猫，第u辆车
void dfs(int k,int u)
{
    //如果当前方案已经大于最优方案，return
    if(u>=res) return;
    if(k==n+1)
    {
        res=u;
        return;
    }

    for(int i=0;i<u;i++)
    {
        if(sum[i]+cat[k]<=m)
        {
            sum[i]+=cat[k];
            dfs(k+1,u);
            sum[i]-=cat[k];
        }
    }
    sum[u]=cat[k];
    dfs(k+1,u+1);
    sum[u]=0;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>cat[i];
    }
    sort(cat+1,cat+1+n);
    reverse(cat+1,cat+1+n);
    dfs(1,0);
    cout<<res;

    return 0;;

}

三刷，像是找到了点感觉，此题非常经典，深入理解dfs的搜索过程

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N=100;
int n,m;
int sum[N];
int w[N];
int res=0x3f3f3f3f;

//目前已经用了u辆车，搜索到了第k只猫
void dfs(int u,int k)
{
    if(u>=res) return;
    if(k==n+1)
    {
        res=u;
        return;
    }

    for(int i=0;i<u;i++)
    {
        if(sum[i]+w[k]<=m)
        {
            sum[i]+=w[k];
            dfs(u,k+1);
            sum[i]-=w[k];
        }
    }

    sum[u]+=w[k];
    dfs(u+1,k+1);
    sum[u]-=w[k];

}


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    sort(w+1,w+n+1);
    reverse(w+1,w+1+n);

    dfs(0,1);
    cout<<res;

    return 0;
}

2023/12/2

完全自己ac的
核心函数：

// 装到第几只猫， 开了几辆车
// 对于每一只猫，都有装进现有车，再开一辆车的方法
void dfs(int x,int cnt)

三个剪枝：
1. 当前方案数大于等于最优解，返回
2. 遍历到最后一只猫，返回
3. 把所有猫的重量按降序排列(只卡最后一个点)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=30;

long long n,m;
// st: 这只小猫有没有被选
int st[N];
long long w[N];
long long a[N];

int res=999;

// 装到第几只猫， 开了几辆车
// 对于每一只猫，都有装进现有车，再开一辆车的方法
void dfs(int x,int cnt)
{

    if(cnt>=res) return;

    if(x==n+1)
    {
        res = min(res, cnt);
        return;
    }


    if(st[x]) return;

    for(int j=1;j<=cnt;j++)
    {
        if(a[j]+w[x] <= m)
        {
            a[j] = a[j]+w[x];
            st[x] = 1;
            dfs(x+1, cnt);
            a[j] = a[j]-w[x];
            st[x] = 0;
        }
    }

    // 新开一辆车
    st[x] = 1;
    a[cnt+1] += w[x];

    dfs(x+1, cnt+1);

    st[x] = 0;
    a[cnt+1] -= w[x];

}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }

    // 要按降序排列，不然会卡最后一个点
    sort(w+1, w+n+1, greater<int>());

    // for(int i=1;i<=n;i++)
    // {
    //     cout<<w[i]<<endl;
    // }

    dfs(1,1);
    cout<<res;



    return 0;
}