小猫爬山

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 30;
int cat[N],sum[N];  //cat表示每只猫的重量，sum表示每辆车已经承载的重量
int n,w;
int ans=N; //ans最坏情况下是每只猫一辆车，共n只猫，因此共n辆车
void dfs(int index,int cnt)
{
    if (cnt>=ans) return;  //如果当前情况下的答案已经超过了之前的答案，这肯定不是最小值了
    if (index==n+1) //如果当前的猫的数量超过了n，说明此时已经到叶子结点
    {
        ans=cnt;
        return;
    }
    for (int i=1;i<=cnt;i++)  //枚举现有的cnt辆车
    {
        if (cat[index]+sum[i]<=w) 
        {
            sum[i]+=cat[index];
            dfs(index+1,cnt);
            sum[i]-=cat[index];  //恢复现场
        }
    }
    sum[cnt+1]=cat[index];  //重新开一辆车装当前的猫
    dfs(index+1,cnt+1);
    sum[cnt+1]-=cat[index];  //恢复现场
}
int main()
{
    cin>>n>>w;
    for (int i=1;i<=n;i++) cin>>cat[i];
    dfs(1,0);  //从第一只猫开始，当前已有的车数是0
    cout<<ans<<endl;
    return 0;
}