题目描述

翰翰和达达饲养了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≤108

输入样例

5 1996
1
2
1994
12
29

输出样例

2

解题思路

本题思路就是dfs 加一个剪枝 还有就是有个小小的贪心
代码上借鉴了y总的

java 代码

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

/**
 * 
 */
public class Main {

    static Integer[] cat;
    static int[] car;
    static int ans;
    static int N, M;

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        cat = new Integer[N];
        car = new int[N];
        ans = N;

        for (int i = 0; i < N; i++) {
            cat[i] = sc.nextInt();
        }

        Arrays.sort(cat, Collections.reverseOrder());

        dfs(0, 0);

        System.out.println(ans);

    }

    public static void dfs(int a, int b) {
        if (b >= ans) return;
        if (a == N) {
            ans = b;
            return;
        }
        for (int i = 0; i < b; i++) {
            if (cat[a] + car[i] <= M) {
                car[i] += cat[a];
                dfs(a + 1, b);
                car[i] -= cat[a];
            }
        }
        car[b] = cat[a];
        dfs(a + 1, b + 1);
        car[b] = 0;
    }

}