分析

• 这是一个背包问题，但是不能使用DP的方式求解，因为背包的时间复杂度为O(N*V)，但这里V（$2^{31}$）的范围太大了，使用DP一定会超时，可以看到N比较小，因此可以使用暴搜来解决。

• 暴搜的话我们可以枚举每个物品选或者不选，则有$2^{46}$种选择，一定会超时，因此需要优化，这里优化的思想是用空间换时间。

• 我们可以大致将N间物品分为两部分，我们算出在第一部分中的物品能凑出的所有质量的集合A，然后对这一部分数据排序，去重。最后暴搜第二部分的数据，比如我们暴搜到某个质量S时，在A中找到小于W-S的最大值，这就是当前质量S能凑出的最大质量。

• 如何在一个之和中找到小于某个数据的最大值呢？可以使用二分。

• 考虑如何剪枝：

（1）优化搜索顺序：优先枚举较大的数，这样之后的分支比较少。

（2）排除等效冗余：无。

（3）可行性剪枝：如果无法加入某件物品，直接回溯。

（4）最优性剪枝：无。

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 46;

int n, m, k;  // k为前一半物品的个数
int w[N];
int weights[1 << 23], cnt = 1;  // weights前一半数组组合得到的质量的集合
int ans;

// u: 当前遍历到的物品编号; s: 当前凑出物品的质量
void dfs1(int u, int s) {

    if (u == k) {
        weights[cnt++] = s;
        return;
    }

    dfs1(u + 1, s);  // 不选物品u
    if ((LL)s + w[u] <= m) dfs1(u + 1, s + w[u]);  // 选物品u
}

void dfs2(int u, int s) {

    if (u == n) {
        int l = 0, r = cnt - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if ((LL)s + weights[mid] <= m) l = mid;
            else r = mid - 1;
        }
        ans = max(ans, s + weights[l]);
        return;
    }

    dfs2(u + 1, s);
    if ((LL)s + w[u] <= m) dfs2(u + 1, s + w[u]);
}

int main() {

    cin >> m >> n;
    for (int i = 0; i < n; i++) cin >> w[i];

    sort(w, w + n);
    reverse(w, w + n);

    k = n / 2;
    dfs1(0, 0);  // 暴搜出第一部分质量集合

    sort(weights, weights + cnt);
    cnt = unique(weights, weights + cnt) - weights;

    dfs2(k, 0);  // 暴搜第二部分

    cout << ans << endl;

    return 0;
}