火星背包

题意解析

本题的背包的容量，以及物品的大小都非常大，无法使用常规的01背包解法。

另外一方面 $N(1 \le N \le 40)$的范围不支持我们使用”搜索+剪枝“来在时限范围内求解。

但是我们可以把所有矿石分为两个部分，分别求解，最后将两个部分的答案合并。

这种方法叫做 $\tt{折半枚举（meet \ in \ middle）}$。

拆分成两个部分后，每个部分的矿石数量为不超过 $20$，可以在 $\mathrm{O}(2^{N/2}N)$ 的复杂度下求得两部分的答案。

我们可以先预处理前半或者后半部分中的选取方法对应的重量和价值总和记为 $w_1, v_1$。这样在另一部分寻找总重 $w_2 \le M - w_1$ 时使 $v_2$ 最大的选取方法即可。

接下来思考如何从枚举得到的 $(w_2, v_2)$ 集合中高效寻找 $\max\{v_2|w2\le M'\}$ 的方法。

首先，可以排除所有 $w_2[i] \le w[j]$ 并且 $v_2[i] \ge v_2[j]$ 的 $j$。这一点可以通过按照 $w_2, v_2$ 的字典序排序后，处理得到。然后剩余的元素都满足 $w_2[i] < w_2[j] \Leftrightarrow v_2[i] < v_2[j]$，要计算 $\max\{v_2|w2\le M'\}$，只需要找到满足 $w_2[i] \le M'$ 的最大的 $i$ 即可。这一点可以通过二分查找高效实现。

令一半矿石的答案个数为 $M(M \le 2^{N/2})$，一次搜索需要
$\mathrm{O}(\log{M})$ 的时间。这个算法总的时间复杂度为 $\mathrm{O}(2^{N/2}N)$.

AC代码

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

using i64 = long long;

struct Info {
    i64 w, v, mask;
    Info() {}
    Info(i64 _w, i64 _v = 0, i64 _mask = 0) : 
        w(_w), v(_v), mask(_mask) {};

    bool operator < (const Info &other) const {
        if (w == other.w) return v < other.v;
        return w < other.w;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    i64 n, m;
    cin >> n >> m;
    vector<i64> w(n), v(n);
    for (int i = 0; i < n; ++i)
        cin >> w[i] >> v[i];
    vector<Info> stB;
    int partA = n / 2, partB = n - n / 2;
    for (int i = 0; i < (1 << partB); ++i) {
        i64 cw = 0, cv = 0;
        for (int j = 0; j < partB and cw <= m; ++j) {
            if (~i >> j & 1) continue;
            cw += w[partA + j];
            cv += v[partA + j];
        }
        if (cw > m) continue;
        stB.emplace_back(cw, cv, i);
    }
    stB.emplace_back(0);
    sort(stB.begin(), stB.end());
    int len = 1;
    for (int i = 1; i < stB.size(); ++i)
        if (stB[len-1].v < stB[i].v)
            stB[len++] = stB[i];
    stB.erase(stB.begin() + len, stB.end());
    i64 maxv = 0, res = 0;
    for (int i = 0; i < (1 << partA); ++i) {
        i64 cw = 0, cv = 0;
        for (int j = 0; j < partA and cw <= m; ++j) {
            if (~i >> j & 1) continue;
            cw += w[j];
            cv += v[j];
        }
        if (cw > m) continue;
        auto p = lower_bound(stB.begin(), stB.end(), Info(m-cw+1)) - stB.begin() - 1;
        if (cv + stB[p].v <= maxv) continue;
        maxv = cv + stB[p].v;
        res = i + (stB[p].mask << partA);  
    }
    cout << maxv << ' ' << __builtin_popcountll(res) << '\n';
    for (int i = 0; i < n; ++i)
        if (res >> i & 1)
            cout << i + 1 << " ";
    return 0;
}

复杂度分析

枚举两部分的答案时间复杂度为 $\mathrm{O}(2^{N/2}N)$。
排序并处理一半元素的时间复杂度为 $\mathrm{O}(2^{N/2}N)$。
将两部分答案合并的时间复杂度为 $\mathrm{O}(2^{N/2}N)$。