dfs解决方案

这道题的总体思路：
因为要求最少的保温箱，移动最少的次数。
首先按照保温箱的容量进行排序，排序完后就可以求的最少的保温箱个数。
但是后面不能直接把后面的保温箱直接移动到容量大的保温箱，因为虽然是最少保温箱个数，但是有可能有多种组合，举个例子

4 3 2 2 2 2 

上面的如果要求货物总量为10个，那么后面四个箱子可以随意两个箱子，那么就可能有12中选择，
那么就要把所有满足要去的保温箱组合求出来，然后再让其中满足条件的组合中已经存放好的货物数量最大，这样需要移动的货物量就会变小。
如何求出满足条件的保温箱组合？通过DFS，但是这样时间复杂度其实是很高的，有O(nn-1n-2*n-k)个，所以还需要对后面剪枝，剪枝方案见代码。总体方案就是这样。

import java.util.*;

public class Main {
    static int sum = 0;  // 代表货物总数
    static int k = 0;
    static ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            sum += a[i];
        }
        Integer[] indexs = new Integer[n];
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
            indexs[i] = i;
        }
        Arrays.sort(indexs, (o1, o2) -> b[o2] - b[o1]);
        int boxSum = 0;  // 临时代表保温箱的货物总数
        while (boxSum < sum) {
            boxSum += b[indexs[k]];
            k++;
        }
        dfs(0, b, indexs, sum, new ArrayList<Integer>());
        int maxAvailableSum = 0;
        for (ArrayList<Integer> boxes : res) {
            int curAvailableSum = 0;
            for (Integer box : boxes) {
                curAvailableSum += a[indexs[box]];
            }
            maxAvailableSum = Math.max(curAvailableSum, maxAvailableSum);
        }
        System.out.format("%d %d", k, sum - maxAvailableSum);

    }

    public static void dfs(int watermark, int[] b, Integer[] indexs, int sum, ArrayList<Integer> box) {
        if (box.size() == k) {
            res.add(new ArrayList<Integer>(box));
            return;
        }
        while (k - box.size() < b.length - watermark) {  // 当剩余可添加的个数还充足时
            if (b[indexs[watermark]] * (k - box.size()) < sum) { // 当剩余的怎么也填不满时,就直接返回
                return;
            }
            box.add(watermark);
            dfs(watermark + 1, b, indexs, sum - b[indexs[watermark]], box);
            box.remove(box.size() - 1);
            watermark++;  // 当前水位往后移动
        }
    }
}