火星背包｜CDQ 分治
原题链接：19337.火星背包
2024-04-17 12:59:40
发布于：新加坡
117阅读
0回复
0点赞
除了折半搜索算法，这里提供一个 CDQ 分治的算法。
关于折半搜索的内容可以参考这两篇题解：
思路分析
这道题是一道超大背包的典型问题，标准做法应该是使用 折半搜索。搜索两次再将两次的答案分别记录下来，最后拼凑出一个正确的答案。但对于超大背包类型问题，在折半搜索的过程需要记录所有的可以达到的点的状态（选和不选的组合）。一个显而易见的问题就是，这会生成许多 又重又不值钱 的状态，然而我们根本就不需要用这些无效状态。
一个可行的做法就是通过分治做法，基于普通折半搜索的基础上加上分治优化，不断地将区间缩小到原来的二分之一，在每一层合并的时候就可以提前先把那些无效状态删除，防止在后续的合并中被使用。
经过测试，在一般数据下，分治可以在几毫秒之内完成。但在极限数据下（即没有任何的无效数据），程序的运行速度相较于 std 会慢一些。
时间复杂度
本算法的渐进时间复杂度与折半搜索的时间复杂度相同，但是常数比较小。
代码解释
这个算法的关键在于利用 cdq 分治的思想，在每一步中合并左右两边的结果，并通过二分查找找到最优解。这样可以在较短的时间内得到问题的解决方案，尤其适用于处理大规模数据。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define int long long
using namespace std;
int n, m, path;
// 用于存放每一个物品，w是物品的重量，v是物品的价值。
struct obj{
int w;
int v;
} arr[55];
struct node{
int weight; // 状态所需要的容量
int value; // 状态的价值
int id; // 记录到达该状态的路径。
/*
例如有五个物品：
a b c d e
选择 a c e 三个物品，可以用二进制表示：10101
id 变量用于存储 背包组合（“10101”） 的二进制形式。
*/
};
// res[i] 表示从起始位置为i的区间的所有可能方案。
vector<node> res[55], combo;
// 按照weight进行排序，weight相同按照value从小到大排序。
bool cmp(node a, node b){
if (a.weight != b.weight) return a.weight < b.weight;
return a.value < b.value;
}
// cdq分治应该是可以过的吧
int cdq(int l, int r){
// 只剩下一个了，直接返回结果，不需要继续递归下去了。
if (l == r){
res[l].clear();
res[l].push_back((node){0, 0, 0});
if (arr[l].w <= m)
res[l].push_back((node){arr[l].w, arr[l].v, 1LL << l});
if (l == 0 && r == n-1) {
path = 1;
return res[l][res[l].size()-1].value;
};
return 0;
}
// 继续cdq分治。
int mid = (l + r) >> 1;
cdq(l, mid); cdq(mid+1, r);
// 计算结果，最终将左右两边结果合并起来
if (n == r - l + 1){
int ans = 0; // 记录最终答案。
// 右边的答案。
auto &right = res[mid + 1];
for (int i=0; i<res[l].size(); i++){
int L = 0, R = right.size() - 1;
while(L <= R){
int amid = (L + R) >> 1;
if (res[l][i].weight + right[amid].weight <= m) L = amid + 1;
else R = amid - 1;
}
if (res[l][i].value + right[L - 1].value > ans){
ans = res[l][i].value + right[L - 1].value;
path = res[l][i].id + right[L-1].id;
}
ans = max(ans, res[l][i].value + right[L - 1].value);
}
return ans;
}
// 合并左右两半部分区间，看一下在限度内的更佳组合。
// 归并的核心思想，将左右两边结果合并成大的结果。
for (int i=0; i<res[l].size(); i++){
for (int j=0; j<res[mid+1].size(); j++){
if (res[l][i].weight + res[mid+1][j].weight <= m){
int s1 = res[l][i].weight + res[mid+1][j].weight;
int s2 = res[l][i].value + res[mid+1][j].value;
// 合并左右两种方案的路径总和。
// 这里使用了二进制的思想，0表示不选，1表示选。
int s3 = res[l][i].id + res[mid+1][j].id;
combo.push_back((node){s1, s2, s3});
} else break;
}
}
// 排序，依照cmp中定义的规则排序。
sort(combo.begin(), combo.end(), cmp);
res[l].clear();
int mi_v = -1;
for (int i=0; i<combo.size(); i++){
if (combo[i].value > mi_v){
mi_v = combo[i].value;
res[l].push_back(combo[i]);
}
}
combo.clear();
return 0;
}
signed main(){
// 加快输入输出，关闭同步流。
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i=0; i<n; i++)
cin >> arr[i].w >> arr[i].v;
// 运行分治算法。
cout << cdq(0, n-1) << " ";
// 输出答案。
vector<int> final_result;
for (int i=0; i<n; i++){
if (path >> i & 1){
final_result.push_back(i+1);
}
}
cout << final_result.size() << endl;
for (auto i : final_result) cout << i << " ";
return 0;
}
这里空空如也
有帮助，赞一个