摘要
Title: 165. 小猫爬山
Tag: DFS
Memory Limit: 64 MB
Time Limit: 1000 ms

165. 小猫爬山

题意

翰翰和达达饲养了 N只小猫，这天，小猫们要去爬山。
经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 W，而 N只小猫的重量分别是 C1、C2……CN。
当然，每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车，翰翰和达达就要付 1美元，所以他们想知道，最少需要付多少美元才能把这 N只小猫都运送下山？
思路

可以看到n特别小，w特别大，所以不是一个背包问题，考虑爆搜
DFS策略
- 遍历目前开的所有车，若能放到这个车，就放
- 若遍历完所有车都放不了，那么就开新车
DFS剪枝
- 如果车的数量比目前答案大了，return
- 优先考虑决策少的，也就是分支少的节点，在此题中，重量大的更少被考虑，所以优先考虑重量大的，也就是事先降序排序

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-03-01 09:22:35
* @FilePath: \Acwing\165\165.cpp
* @LastEditTime: 2023-03-01 10:14:16
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 20, INF = 0x3f3f3f3f;
int c[N], sum[N];
int n, w;
int ans = INF;
void dfs(int u, int k)
{
    if (k >= ans)
        return;
    if (u == n + 1)
    {
        ans = k;
        return;
    }
    for (int i = 0; i < k; ++i)
    {
        if (c[u] + sum[i] <= w)
        {
            sum[i] += c[u];
            dfs(u + 1, k);
            sum[i] -= c[u];
        }
    }
    sum[k] = c[u];
    dfs(u + 1, k + 1);
    sum[k] = 0;
}

signed main()
{
    IOS;
    cin >> n >> w;
    for (int i = 1; i <= n; ++i)
    {
        cin >> c[i];
    }
    sort(c + 1, c + 1 + n, greater<int>());
    dfs(1, 1);
    cout << ans << '\n';
    return 0;
}

165. 小猫爬山

题意

思路

代码