165. 小猫爬山

Powered by:NEFU AB-IN

Link

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;
  }