【DFS】小猫爬山

题目

165. 小猫爬山 - AcWing题库

---

翰翰和达达饲养了 $N$ 只小猫，这天，小猫们要去爬山。

经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为 $W$ ，而 $N$ 只小猫的重量分别是 $C_1、C_2……C_N$ 。

当然，每辆缆车上的小猫的重量之和不能超过 $W$ 。

每租用一辆缆车，翰翰和达达就要付 $1$ 美元，所以他们想知道，最少需要付多少美元才能把这 $N$ 只小猫都运送下山？

输入格式

第 $1$ 行：包含两个用空格隔开的整数， $N$ 和 $W$ 。

第 $2..N+1$ 行：每行一个整数，其中第 $i+1$ 行的整数表示第 $i$ 只小猫的重量 $C_i$ 。

输出格式

输出一个整数，表示最少需要多少美元，也就是最少需要多少辆缆车。

数据范围

$1 \le N \le 18$ ,
$1 \le C_i \le W \le 10^8$

输入样例：

5 1996
1
2
1994
12
29

输出样例：

2

解题

方法一：DFS 回溯 剪枝

思路

首先根据本题的数据范围（$1 \le N \le 18$）可以基本判断出本题应该用DFS+剪枝求解。

具体来说：从前向后枚举每一只小猫，对于每一只小猫，枚举把它放在哪一辆车内。搜索树如下（ $cat = 0 \dots n-1$ ）：

暴搜：$dfs(car, cat)$ （ $car$ 表示当前有多少辆车， $cat$ 表示当前尝试枚举到的小猫下标）：

• 出口：当 $cat$ 枚举越界（ $cat \ge n$ ）时，更新最少所需要车的数量，退出程序。
• 枚举第 $0 \dots car-1$ 辆车：
  • 如果把猫 $cat$ 放在当前这辆车上没有超载：
    • 尝试放上去，递归下一只猫（ $dfs(car, cat + 1)$ ）。
    • 回溯（还原当前车的重量）。
• 开一辆新车放猫，递归下一只猫（ $dfs(car + 1, cat + 1)$ ）。
• 回溯（删掉新车）。

剪枝：

1. 优化搜索顺序：体重较重的猫有更大可能占满一辆车，这可以让之后尽可能少的猫选择放在该车上，所以可以有效地减少搜索的分支，所以应该尽可能优先枚举体重较重的猫（把猫按体重降序排序）。
2. 可行性剪枝：如果当前猫放在某辆车上重量超过了 $W$，就应该直接剪枝。
3. 最优性剪枝：如果当前车的数量已经大于等于维护的最优解的车的数量了，就应该直接剪枝。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n, w;
    static Integer[] cats; // 基础类型数组不能直接排序 所以用包装类数组
    static int[] cars; // 维护每辆车当前的的总重量
    static int ans = 20;
    
    static void dfs(int car, int cat) {
        if (car >= ans) return; // 最优性剪枝
        if (cat == n) {
            ans = car; // 更新最优方案
            return;
        }
        int curr = cats[cat];
        for (int i = 0; i < car; ++i) {
            if (cars[i] + curr <= w) { // 可行性剪枝
                cars[i] += curr;
                dfs(car, cat + 1);
                cars[i] -= curr;
            }
        }
        cars[car] = curr;
        dfs(car + 1, cat + 1);
        cars[car] = 0;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        w = (int) in.nval;
        cats = new Integer[n];
        cars = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            cats[i] = (int) in.nval;
        }
        Arrays.sort(cats, Comparator.reverseOrder()); // 优化搜索顺序
        dfs(0, 0);
        System.out.println(ans);
    }
}