J 小奇采药 LibreOJ - 6559
一个01背包, 但没那么简单, 仔细一看数据范围, 居然背包容量能到 1e9, 但物品数只有150个, 显然这道题是用 DFS 来搜索结果。
但各位在赛后查看时可能会发现有人(指LibreOJ)用 01背包 硬过了, 只需要加上这条优化：
N = 1e5 + 10;
if (m > N)
{
m /= 10000;
for (int i = 1; i <= n; i++)
v[i] /= 10000;
}这是因为题目中的一句话 “保证 在限制范围内均匀随机生成”, 类似的在 2021CCPC河南省赛也有一道题出现这个条件。往往代表着题目数据不强, 暗示你可以有一些 大胆 的想法, 而这道题, 就可以强制把大于 N 的给缩小到 N 以内来做, 当然只是体积, 价值还得是原来的。
算是奇技淫巧, 但也不得不品尝, 毕竟认真 WA 多少次也比不上一个偷跑的 AC。
当然这都是在你不会正解的情况下, 真要卡还是很简单的, 接下来介绍正解：
正常 01背包 是枚举物品再枚举体积, 而 DFS 就直接枚举所有可行方案, 每个物品有选和不选两种操作, 最坏时间复杂度为 , 这当然不可能过, 但也不是所有情况都成立。
DFS函数参数为 当前方案的已用体积和总价值。
枚举前先将 数组从大到小排序, 这样把分支数量小的部分放前面会优化一些复杂度。
其次, 对于先选 A, 后选 B 与 先选 B, 后选 A 两种情况是等价的, 也就是说我们应该用组合的方式搜索, 而非排列的方式。
在代码中就是为 DFS函数增加一个参数 last表示上一步搜到了第几个物品, 接下来就从 last 继续往后搜。只看当前的物品, 递归搜索选和不选两种情况即可。
此时就已经可以过前 9 个样例了, 接下来就是更加具有启发性的剪枝优化操作。回忆一下生日蛋糕题目, 当时是用一个 数组来提前把 的情况减掉, 即当后面所有选择都选体积最小的方案, 依然会超出范围, 说明当前路线就不必选择。
同理, 这里也定义一个 数组, 如果当前 都小于之前得出的 , 那么就直接减掉。
也可以再定义一个 数组, 如果当前 , 哪怕把后面所有的物品都拿上也在背包容量范围内, 那么就直接全拿了返回, 不再继续搜索。
总结下来, 这两个优化都属于 前瞻性剪枝。
对于这方面更体系的学习可以去看acwing提高课的搜索剪枝部分。
代码
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL f[N];
LL n, m;
LL res;
LL sumv[N], sumw[N];
struct Item {
LL v, w;
bool operator<(const Item &W) {
return v >= W.v;
}
} item[N];
void dfs(LL j, LL w, int last) {
if (w + sumw[last] < res)
return;
if (j + sumv[last] <= m) {
res = max(res, w + sumw[last]);
return;
}
res = max(res, w);
if (j + item[last].v <= m)
dfs(j + item[last].v, w + item[last].w, last + 1);
dfs(j, w, last + 1);
}
void solve() {
memset(f, 0, sizeof f);
res = -0x3f3f3f3f;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> item[i].v >> item[i].w;
sort(item + 1, item + 1 + n);
for (int i = n; i >= 1; i--) {
sumv[i] = sumv[i + 1] + item[i].v;
sumw[i] = sumw[i + 1] + item[i].w;
}
dfs(0, 0, 1);
cout << res << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--)
solve();
return 0;
}