[数据结构与算法]AcWing 165 小猫爬山

题解：
复习一下$DFS$，考虑到后面的图论和数据结构好多都是需要搜索的，所以这里再巩固一下，毕竟自己的搜索实在是一言难尽QAQ。
带有回溯（还原现场）类型的题目，其实关键就是确定搜索边界+搜索的方法，这个题目的边界肯定是全部的猫都被放到了车上，然后我们的搜索方法是：当前对于编号为$now$的猫：

• 尝试把他放在第$i$个车上，$1\le i\le cnt$，$cnt$为当前我们租的车数目。如果放的下，我们就递归$dfs(now+1,cnt)$
• 尝试把他单独放在一个车上，那就是$dfs(now+1,cnt+1)$

当$now=N+1$时，也就是到达了边界。
同时为了缩小搜索规模，我们认为当$cnt\ge ans$时就结束递归。同时，体重大的猫肯定比体重小的更难安排，所以我们优先放体重大的猫。

#include <bits/stdc++.h>

#define ill __int128
#define ll long long
#define PII pair <ll,ll>
#define ull unsigned long long
#define me(a,b) memset (a,b,sizeof(a))
#define rep(i,a,b) for (int i = a;i <= b;i ++)
#define req(i,a,b) for (int i = a;i >= b;i --)
#define ios std :: ios :: sync_with_stdio(false)

const double Exp = 1e-9;
const int INF = 0x3f3f3f3f;
const int inf = -0x3f3f3f3f;
const ll mode = 1000000007;
const double pi = 3.141592653589793;

using namespace std;

const int maxn = 100;

int n, c[maxn], w, sum[maxn];
int ans = 0;

bool cmd(int x, int y)
{
    return x > y;
}

void dfs(int num, int cnt)
{
    if (cnt >= ans) return ;
    if (num == n + 1) {
        ans = min(ans, cnt);
        return ;
    }
    for (int i = 1;i <= cnt;i ++) {
        if (sum[i] + c[num] <= w) {
            sum[i] += c[num];
            dfs(n + 1, cnt);
            sum[i] -= c[num];
        }
    }
    sum[cnt + 1] = c[num];
    dfs(num + 1, cnt + 1);
    sum[cnt + 1] = 0;
    return ;
}

int main()
{
    scanf ("%d%d",&n, &w);
    for (int i = 1;i <= n;i ++) scanf ("%d",&c[i]);
    sort(c + 1, c + 1 + n, cmd);
    ans = n;
    dfs(1, 0);
    printf ("%d\n", ans);
    return 0;
}