C++ 中的中途相遇算法

引言

当寻找一个需要处理大量选项或大量数据的问题的解决方案时，暴力破解法可能需要太长时间。折半查找方法是一种有效地将问题拆分的方法，它比尝试顺序解决所有问题更简单。

问题陈述

在这个问题中，我们需要检索一组整数，其和将接近但不超过指定的目标 S。

示例

示例 1

• 输入： set[] = {45, 34, 4, 12, 5, 2}, S = 42
• 输出 41

子集 {34, 5, 2} 给出最大的和 41，它 ≤ S。

示例 2

• 输入： set[] = {3, 34, 4, 12, 5, 2}, S = 10
• 输出 10

子集 {2, 3, 5} 的和为 10，这是最大可能的 ≤ S。

优化方法：折半查找

当 N 设置为小数字但仍足够高以进行暴力破解时，我们实施折半查找。

该解决方案将大问题分解为两个较小的可解决组件，它们独立解决，之后以简单的方式集成解决方案。

步骤：

1. 将 S 数据集分成两半
   • A (前 N/2 个元素)
   • B (剩余的 N/2 个元素)
2. 计算两半的所有子集和
   • 将 A 的所有可能和保存在数组 X 中。
   • 将 B 的所有可能和保存在数组 Y 中。
   • 每个数组最多有 2^(N/2) 个元素，而不是 2ⁿ。
3. 合并结果以找到最佳子集和
   • 对数组 Y 进行排序。
   • 对于 X 中的每个和 x，找到 Y 中最大的 y，使得 x + y ≤ S。
   • 使用二分查找 (O(log 2^(N/2))) 代替暴力破解 (O(2^(N/2)))。

时间复杂度分析

• 生成 A 和 B 的所有子集和： O(2^(N/2))
• 对 Y 排序： O(2^(N/2) log(2^(N/2)))
• 使用二分查找搜索最佳和： O(2^(N/2) log(2^(N/2)))
• 最终复杂度： O(2^(N/2) * N

程序

输出

Largest subset sum not exceeding 42 is: 41   

为什么折半查找算法更好？

• 暴力破解： O(2ⁿ) = 10¹² (太慢)
• 折半查找： O(2ⁿ/² * n) ≈ 10⁶ (快得多)

这使得 N 可以增加到 40，这使其成为一个完美的选择。

结论

总之，当 N 对于暴力破解方法来说变得非常大，但对于优化技术来说仍可管理时，折半查找算法对于子集和问题是有效的。

通过将问题分解为更小的尺寸，计算所需的上子集和，对较小的和进行排序，并对相应的下和执行二分查找，可以以非常低的复杂性获得高效的结果。