$$\color{Red}{小猫爬山——DFS之剪枝}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

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

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

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

索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是 C1、C2……CN。

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

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

输入格式

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

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

输出格式

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

数据范围

1 ≤ N ≤ 18

1 ≤ Ci ≤ W ≤ 10 ^ 8

输入样例：

5 1996
1
2
1994
12
29

输出样例：

2

思路

这道题从剪枝上讲了一个很朴素也是以前就在应用的一个点，即dfs开局判断当前搜索是否已经比目前最优解更差或相同，如果条件满足则直接剪枝。

这个剪枝思路并不是特别独特，但是y总提到了一个新的剪枝策略，即，优先遍历让根节点分支更少的情况，即优先搜最重的小猫，这样让整个树可以更快的回溯，达到搜索的效率更快的目的。

这道题第一眼以为是背包，但背包问题是一个背包，选最优的方案拿最大价值，这道题是多个背包，考虑最少的背包把全部物品装完。故应该采用搜索，而写完题解突然纠结最后的返回数量和实际形参的对应关系应该是怎么样的，其实形参代表目前考虑是否开新组的下标，但下标从0开始记数，故return的时候可以直接返回当前考虑的新组下标，即组数。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int N = 20, n, m, ans = N;
    static int[] cat = new int[N];
    static int[] group = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void dfs(int catIndex, int groupCount) {
        if (groupCount >= ans) return;
        if (catIndex == n) {
            ans = groupCount;
            return;
        }
        for (int i = 0; i < groupCount; i++)
            if (cat[catIndex] + group[i] <= m) {
                group[i] += cat[catIndex];
                dfs(catIndex + 1, groupCount);
                group[i] -= cat[catIndex];
            }
        group[groupCount] = cat[catIndex];
        dfs(catIndex + 1, groupCount + 1);
        group[groupCount] = 0;
    }

    public static void main(String[] args) throws IOException {
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 0; i < n; i++) cat[i] = Integer.parseInt(br.readLine());
        dfs(0, 1);
        System.out.println(ans);
    }
}