火星背包｜折半搜索

黄老师已经讲解了折半搜索的基本原理和优化思想，这里就不多说了。
本文旨在提供一个dfs形式的折半搜索，会比双层for循环读起来更加友好。

具体请自行阅读以下代码，注释已经完善了：

// 不得不说，MInM的代码是真的长。写起来也好麻烦。
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;

int n, m, mid;
int w[55], v[55];
int maxa, maxb;

// node 用于记录dfs可以组合出来的所有状态。
struct node{
    int weight;  // 状态所需要的容量
    int value;  // 状态的价值
    int id;  // 记录到达该状态的路径。
    /*
        例如有五个物品：
        a b c d e
        选择 a c e 三个物品，可以用二进制表示：10101
        id 变量用于存储 背包组合（“10101”） 的二进制形式。
    */
}; 
// 用于存储两次dfs所有可以到达的节点。
vector<node> ans1, ans2;

// 按照weight进行排序，weight相同按照value从小到大排序。
bool cmp(node a, node b){
    if (a.weight == b.weight)
        return a.value < b.value;
    return a.weight < b.weight;
}

// 第一次深度优先搜索。
void dfs1(int L, int R, int weight, int value, int id){
    if (weight > m) return ;
    if (L > R){
        // 寻找是否有更优的，没有的话就
        ans1.push_back((node){weight, value, id});
        return ;
    }
    // 两种选择，选物品或者不选物品。
    dfs1(L+1, R, weight, value, id);
    // 这里的位运算可以自己动手画一下。
    dfs1(L+1, R, weight + w[L], value + v[L], (1LL << (L-1LL)) + id);
    return ;
}

// 第二次深度优先搜索。
void dfs2(int L, int R, int weight, int value, int id){
    if (weight > m) return ;
    if (L > R){
        ans2.push_back((node){weight, value, id});
        return ;
    }
    // 两种选择，选物品或者不选物品。
    dfs2(L+1, R, weight, value, id);
    dfs2(L+1, R, weight + w[L], value + v[L], (1LL << (L-1LL)) + id);
    return ;
}

signed main(){
    // 加快输入输出，关闭同步流。
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i=1; i<=n; i++)
        cin >> w[i] >> v[i];

    // 折半搜索
    mid = n >> 1;
    dfs1(1, mid, 0, 0, 0);
    dfs2(mid + 1, n, 0, 0, 0);

    // 按照规则排序。
    sort(ans1.begin(), ans1.end(), cmp);

    // 表示截至目前得到的最大value。
    int value = 0;  

    // 将ans1中的无效元素清除（非最优解）
    vector<node> tmpath;
    tmpath.push_back((node){-1, -1, -1});
    for (int i=0; i<ans1.size(); i++){
        if (tmpath.back().value < ans1[i].value){
            tmpath.push_back(ans1[i]);
        }
    }

    // 二分拼接前后两半部分的答案。
    int maximum = 0, res = 0;
    for (int i=0; i<ans2.size(); i++){
        int weight = m - ans2[i].weight;
        // 寻找最后的，满足 m - weight
        int l = 1, r = tmpath.size() - 1;
        int ans = 0;
        // 寻找最优解，用二分优化。
        while(l <= r){
            int mid = (l + r) >> 1;
            if (tmpath[mid].weight <= weight){
                l = mid + 1;
                ans = mid;
            } else r = mid - 1;
        }
        // 更新答案
        if (ans != 0 && tmpath[ans].value + ans2[i].value > maximum){
            maximum = tmpath[ans].value + ans2[i].value;
            // 将前后两半部分的路径相加，就可以获得最终的路径。
            // 详情见二进制的加减运算。
            res = (ans2[i].id) + (tmpath[ans].id);
        }
    }
    
    // 结果输出
    vector<int> final_result;
    for (int i=0; i<n; i++){
        if (res >> i & 1){
            final_result.push_back(i+1);
        }
    }

    cout << maximum << " " << final_result.size() << endl;
    for (auto i : final_result) cout << i << " "; 
    return 0;
}