思路

1. 直接DFS复杂度$O(2^N)$；背包容量$W=2^{31}-1$过大，复杂度$O(N*W)$
2. 初态为0，末态为最大总和，考虑使用双向搜索，分成两段搜索各自能凑出的总和，再合并求最大值，平分时复杂度$O(2^{\frac N 2})$
   • 将数据分成两半，先搜前一半的能凑出的所有数字，记录到数组（注意去重）
   • 再搜后一半，每个分支求的最终总和$sum$，与输入的$W$作差得到剩余可添加的最大值
   • 二分查找前一半组成的数，找到不超过$W$的最大值，与$sum$相加得到本分支能凑成的最大值
   • 多个分支的最终值取最大值
3. 去重可以使用HashSet，搜索前先降序排列数组，从大到小搜可以减少搜索分支
4. 注意虽然$1 \leq W,G[i] \leq 2^{31}-1$不会超int范围，但是搜索过程中计算$sum + G[i]$时有可能爆int

代码

import java.lang.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, w, ans;
    static int[] g = new int[50];
    static Integer[] sumBefore;
    static HashSet<Integer> set = new HashSet<>();

    public static void dfs1(int s, int sum) {
        if (s > (n >> 1)) {  // 前一半遍历终点 g[n/2]
            set.add(sum);  // 扔到HashSet去重
            return;
        }
        dfs1(s + 1, sum);  // 不选当前数字 递归下一层
        if ((long) sum + g[s] <= w) {  // 判断是否可选
            dfs1(s + 1, sum + g[s]);  // 可选则更新sum 递归下一层
        }
    }

    public static void dfs2(int s, int sum) {
        if (s > n) {  // 后一半的递归终点 g[n]
            // x是当前sum还能增加的最大值 二分查找前一半能凑出的数 找到不超过x的最大值
            int l = 0, r = sumBefore.length - 1, x = w - sum;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (sumBefore[mid] <= x) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            if (sumBefore[l] <= x) {  // 如果找到了 与当前sum相加得到本分支能凑成的最大值 再与已记录答案取最大值
                ans = Math.max(ans, sum + sumBefore[l]);
            }
            return;
        }
        dfs2(s + 1, sum);  // 不选
        if ((long) sum + g[s] <= w) {  // 可选则选 并更新sum
            dfs2(s + 1, sum + g[s]);
        }
    }

    public static void main(String[] args) {
        w = scanner.nextInt();
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            g[i] = scanner.nextInt();
        }
        Arrays.sort(g, 1, n + 1);  // 升序排列
        for (int i = 1, j = n; i < j; i++, j--) {  // 反转为逆序
            int t = g[i];
            g[i] = g[j];
            g[j] = t;
        }
        dfs1(1, 0);  // 搜前一半 起点为1 终点为n/2 把能凑出的数都存入HashSet
        sumBefore = new Integer[set.size()];
        set.toArray(sumBefore);  // 从set转到数组 便于实现二分查找
        Arrays.sort(sumBefore);  // set本身无序 注意重新排序
        dfs2((n >> 1) + 1, 0);  // 搜后一半 起点为n/2+1 终点为n 对每个能凑出的sum 找前一半是否有能匹配出最大值的
        System.out.println(ans);
    }
}