除了折半搜索算法，这里提供一个 CDQ 分治的算法。 关于折半搜索的内容可以参考这两篇题解： 火星背包 - アイドル 火星背包｜折半搜索 - Macw 思路分析 这道题是一道超大背包的典型问题，标准做法应该是使用 折半搜索。搜索两次再将两次的答案分别记录下来，最后拼凑出一个正确的答案。但对于超大背包类型问题，在折半搜索的过程需要记录所有的可以达到的点的状态（选和不选的组合）。一个显而易见的问题就是，这会生成许多 又重又不值钱 的状态，然而我们根本就不需要用这些无效状态。 一个可行的做法就是通过分治做法，基于普通折半搜索的基础上加上分治优化，不断地将区间缩小到原来的二分之一，在每一层合并的时候就可以提前先把那些无效状态删除，防止在后续的合并中被使用。 经过测试，在一般数据下，分治可以在几毫秒之内完成。但在极限数据下（即没有任何的无效数据），程序的运行速度相较于 std 会慢一些。 时间复杂度 本算法的渐进时间复杂度与折半搜索的时间复杂度相同，但是常数比较小。 代码解释 这个算法的关键在于利用 cdq 分治的思想，在每一步中合并左右两边的结果，并通过二分查找找到最优解。这样可以在较短的时间内得到问题的解决方案，尤其适用于处理大规模数据。

黄老师已经讲解了折半搜索的基本原理和优化思想，这里就不多说了。 本文旨在提供一个dfs形式的折半搜索，会比双层for循环读起来更加友好。 具体请自行阅读以下代码，注释已经完善了：

题意解析 本题的背包的容量，以及物品的大小都非常大，无法使用常规的01背包解法。 另外一方面 N(1≤N≤40)N(1 \le N \le 40)N(1≤N≤40)的范围不支持我们使用”搜索+剪枝“来在时限范围内求解。 但是我们可以把所有矿石分为两个部分，分别求解，最后将两个部分的答案合并。 这种方法叫做 折半枚举（meet in middle）\tt{折半枚举（meet \ in \ middle）}折半枚举（meet in middle）。 拆分成两个部分后，每个部分的矿石数量为不超过 202020，可以在 O(2N/2N)\mathrm{O}(2^{N/2}N)O(2N/2N) 的复杂度下求得两部分的答案。 我们可以先预处理前半或者后半部分中的选取方法对应的重量和价值总和记为 w1,v1w_1, v_1w1 ,v1 。这样在另一部分寻找总重 w2≤M−w1w_2 \le M - w_1w2 ≤M−w1 时使 v2v_2v2 最大的选取方法即可。 接下来思考如何从枚举得到的 (w2,v2)(w_2, v_2)(w2 ,v2 ) 集合中高效寻找 max⁡{v2∣w2≤M′}\max\{v_2|w2\le M'\}max{v2 ∣w2≤M′} 的方法。 首先，可以排除所有 w2[i]≤w[j]w_2[i] \le w[j]w2 [i]≤w[j] 并且 v2[i]≥v2[j]v_2[i] \ge v_2[j]v2 [i]≥v2 [j] 的 jjj。这一点可以通过按照 w2,v2w_2, v_2w2 ,v2 的字典序排序后，处理得到。然后剩余的元素都满足 w2[i]<w2[j]⇔v2[i]<v2[j]w_2[i] < w_2[j] \Leftrightarrow v_2[i] < v_2[j]w2 [i]<w2 [j]⇔v2 [i]<v2 [j]，要计算 max⁡{v2∣w2≤M′}\max\{v_2|w2\le M'\}max{v2 ∣w2≤M′}，只需要找到满足 w2[i]≤M′w_2[i] \le M'w2 [i]≤M′ 的最大的 iii 即可。这一点可以通过二分查找高效实现。 令一半矿石的答案个数为 M(M≤2N/2)M(M \le 2^{N/2})M(M≤2N/2)，一次搜索需要 O(log⁡M)\mathrm{O}(\log{M})O(logM) 的时间。这个算法总的时间复杂度为 O(2N/2N)\mathrm{O}(2^{N/2}N)O(2N/2N). AC代码 复杂度分析 枚举两部分的答案时间复杂度为 O(2N/2N)\mathrm{O}(2^{N/2}N)O(2N/2N)。 排序并处理一半元素的时间复杂度为 O(2N/2N)\mathrm{O}(2^{N/2}N)O(2N/2N)。 将两部分答案合并的时间复杂度为 O(2N/2N)\mathrm{O}(2^{N/2}N)O(2N/2N)。