I题：一题无法DP的背包题

由于物品的大小和容量到达了 显然无法额外创建空间dp。

而对于 我们不难想到这题可以暴力写， 但是纯暴力或者DFS的时间复杂度会到达 在最坏情况下显然会爆掉，所以这题需要运用 分治策略 (Meet in the middle) ，换句话说就是 折半搜索 ，可以将复杂度 降为

再加上搜索，那么这题暴力写法的总时间复杂度是

也就是

代码实现：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define endl '\n'

ll w, n;
vector<ll> a;

//暴力枚举所有子集合的和
vector<ll> brust(const vector<ll>& arr) {
    int sz = arr.size();
    vector<ll> sum;
    for (int i = 0; i < (1 << sz); i++) {
        ll s = 0;
        for (int j = 0; j < sz; j++) {
            if (i & (1 << j)) s += arr[j];
        }
        sum.push_back(s);
    }
    return sum;
}

void sol() {
    cin >> w >> n;
    a.resize(n);
    ll ss = 0;
    for (ll &wt : a) {
        cin >> wt;
        ss += wt;
        if (wt == w) {
            cout << wt << endl;
            return;
        }
    }
    if (ss <= w) {
        cout << ss << endl;
        return;
    }
    vector<ll> l(begin(a), begin(a) + n/2);
    vector<ll> r(begin(a) + n/2, end(a));
    vector<ll> ls = brust(l);

    vector<ll> rs = brust(r);
    sort(begin(rs), end(rs));
  
    //折半搜索
    ll ans = 0;
    for (ll sum : ls) {
        if (sum > w) continue;
        auto it = upper_bound(begin(rs), end(rs), w - sum) - 1;
        ans = max(ans, sum + *it);
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    sol();
    return 0;
}