超大背包问题

概念

超大背包问题是指物品数量 $n$ 较小（通常 $n\le 40$）但背包容量 $W$ 极大（如 $W\le 10^{15}$）的 0-1 背包问题。此时标准的 $O(nW)$ DP 无法在时间和空间上承受，需要使用折半搜索（Meet in the Middle）等技巧。

核心思想

折半搜索（Meet in the Middle）

将 $n$ 个物品分成两半（各约 $n/2$ 个），分别枚举每一半的所有子集组合（每半最多 $2^{n/2}$ 种），记录每种选法的总重量和总价值。

1. 前半部分：枚举所有 $2^{n/2}$ 种子集，记录 (总重量, 总价值) 对。
2. 后半部分：同样枚举所有 $2^{n/2}$ 种子集。
3. 合并：对前半部分按重量排序，对后半部分的每种选法，在前半部分中二分查找剩余容量内价值最大的组合。

合并前需要对前半部分做预处理：按重量排序后，去除被”支配”的方案（即重量更大但价值不更高的方案），使得价值随重量单调递增，从而可以高效二分。

时间复杂度

$O(2^{n/2}\cdot \log (2^{n/2}))=O(n\cdot 2^{n/2})$

相比暴力枚举全部子集的 $O(2^n)$，折半搜索将指数减半。

适用场景

• 物品数量少（$n\le 40$）但容量极大的 0-1 背包
• 无法用常规 DP 处理的大值域背包问题
• 其他需要折半枚举 + 合并的搜索问题

参考

• 超大背包问题详解