洛谷 P10483 小猫爬山 完整题解

一、题目检察

  P10483 小猫爬山 - 洛谷

    二、解题思绪

  我们将采取递归 + 剪枝的思想：
  sum数组存放每辆车当前载重。
  每次新考虑一只小猫时，我们实验把它放进每个可以放进的缆车中（需要回溯）

1. for (int i = 0; i < k; i++) {
2.         if (sum[i] + c[u] <= w) {
3.                 sum[i] += c[u];
4.                 dfs(u + 1, k);
5.                 sum[i] -= c[u];
6.         }
7. }

复制代码

我们还要再实验为它单独新开一辆缆车，不然会错（也要回溯）

1. sum[k] = c[u];
2. dfs(u + 1, k + 1); // 再开一个缆车
3. sum[k] = 0;

复制代码

最后我们需要更新答案和剪枝

1. if (k >= ans) return; // 如果缆车数量不如当前最佳答案直接剪枝
2. if (u == n) ans = k; // 小猫都装完了

复制代码

    三、代码

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int N = 20;
5. int c[N], sum[N];
6. int n, w, ans;
8. void dfs(int u, int k) { // u = 第 u 只小猫, k = 缆车数量
9.         if (k >= ans) return; // 如果缆车数量不如当前最佳答案直接剪枝
10.         if (u == n) ans = k; // 小猫都装完了
11.         for (int i = 0; i < k; i++) {
12.                 if (sum[i] + c[u] <= w) {
13.                         sum[i] += c[u];
14.                         dfs(u + 1, k);
15.                         sum[i] -= c[u];
16.                 }
17.         }
18.         sum[k] = c[u];
19.         dfs(u + 1, k + 1); // 再开一个缆车
20.         sum[k] = 0;
21. }
23. int main() {
24.         cin >> n >> w;
25.         ans = n;
26.         for (int i = 0; i < n; i++) {
27.                 cin >> c[i];
28.         }
29.         dfs(0, 0);
30.         cout << ans;
31.         return 0;
32. }

复制代码

   四、测试结果