$$\color{Red}{送礼物——DFS之双向DFS}$$

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

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

题目介绍

达达帮翰翰给女生送礼物，翰翰一共准备了 N 个礼物，其中第 i 个礼物的重量是 G[i]。

达达的力气很大，他一次可以搬动重量之和不超过 W 的任意多个物品。

达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

输入格式

第一行两个整数，分别代表 W 和 N。

以后 N 行，每行一个正整数表示 G[i]。

输出格式

仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。

数据范围

1 ≤ N ≤ 46

1 ≤ W ,G[i] ≤ 2 ^ 31 − 1

输入样例：

20 5
7
5
4
18
1

输出样例：

19

思路

这道题是DFS的双向深搜，其实和我的字符变换题解【双向广搜】不太一样，我觉得严格意义上这道题是在第一次的基础上搜第二次，从而把O(2 ^ n)优化到了 2 * O(2 ^ (2 / n))【这里没有算上二分的复杂度】

具体而言，这道题乍一看可能是背包问题，但是背包问题的复杂度是 O(n * m) ，而这道题的 m 最大可以到 2 ^ 31 − 1 加上 n 最大为46，必然会超时。

而如果直接爆搜，复杂度就是 O(2 ^ n)，也难以接受。

故需要使用优化手段优化。

这道题我们可以使用分治的思想，先搜一半的数，然后存起来它能获得的求和数组，然后去重【因为我们只需要找到一组解】。

在这个数组的基础上，搜后半组数字，如果搜完全部的数，求和的情况下能满足小于等于 达达的力气【二分搜索】，就试着更新一下答案。

同时这道题我们发现第二个搜索的二分，导致后半段的复杂度被扩大为m【二分的次数】 * O(2 ^ (n / 2))，可见每当减少一次二分，就能大大优化后半段的复杂度， 故我们可以摊几个数字到前面无二分二分的第一次搜索。

题毕，具体代码细节，写了详细的注释。

java

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

public class Main {

    static int n, m, k, cnt, N = 50;
    static int[] w = new int[N];
    static int[] items = new int[1 << 25];
    static long ans;

    static void reverse() {
        for (int i = 0; i < n / 2; i++) {
            int temp = w[i];
            w[i] = w[n - i - 1];
            w[n - i - 1] = temp;
        }
    }

    static int unique() {
        int t = 0;
        for (int i = 0; i < cnt; i++) {
            if (t == 0 || items[i] != items[i - 1]) {
                items[t++] = items[i];
            }
        }
        return t;
    }

    /**
     * 找寻前 k 个数字 能组成哪些和
     *
     * @param u 当前将要枚举的数的下标 同时也代表目前枚举了多少个数
     * @param s 当前搜索 0 -> u-1 的数的一种情况  和为 s
     */
    static void dfs_1(int u, int s) {
        if (u >= k) {
            items[cnt++] = s;
            return;
        }
        // 分别枚举选和不选的情况
        if ((long) s + w[u] <= m) dfs_1(u + 1, s + w[u]);
        dfs_1(u + 1, s);
    }

    /**
     * 找寻 第 k + 1 的数 -> 第 n 个数 能组成哪些和
     * 同时更新满足 小于等于 m 的答案
     *
     * @param u 当前将要枚举的数的下标 同时也代表目前枚举了多少个数
     * @param s 当前搜索 0 -> u-1 的数的一种情况  和为 s
     */
    static void dfs_2(int u, int s) {
        if (u >= n) {
            int l = 0, r = cnt - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if ((long) s + items[mid] <= m) l = mid;
                else r = mid - 1;
            }
            if ((long) items[l] + s <= m) ans = Math.max(ans, s + items[l]);
            return;
        }
        // 分别枚举选和不选的情况
        if ((long) s + w[u] <= m) dfs_2(u + 1, s + w[u]);
        dfs_2(u + 1, s);
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        m = Integer.parseInt(s1[0]);
        n = Integer.parseInt(s1[1]);
        for (int i = 0; i < n; i++) {
            w[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(w, 0, n);
        reverse();
        k = n / 2 + 2; // 见上文解析部分 这里是均摊复杂度
        dfs_1(0, 0);

        // 第二次搜索 先去重排序
        Arrays.sort(items, 0, cnt);
        cnt = unique();

        // 起点为开始枚举第 k+1 个数【下标为k】
        dfs_2(k, 0);
        System.out.println(ans);
    }
}