algorithm - 子集中具有最大元素数的背包

Question

我有一个整数数组，我需要找到这个数组的一个子集，其中最大 3 个元素等于 W。

我可以用背包解决这个问题吗？或者我需要计算数组的每个 1-2-3 元素组合？

已经谢谢了

Answer 1

要寻找总和的 3 个元素W，这正是3SUM 问题。

它可以通过以下任一方式在 O(n ² ) 时间内解决：

• 将每个数字插入到哈希表中，然后，对于两个数字a和的每个组合b，检查哈希表中是否W-a-b存在。

• 对数组进行排序，然后，对于每个 element a，寻找两个元素，总和为W-a使用来自任一侧的 2 个迭代器。

如果整数范围在范围内[-u, u]，您可以使用 O(n + u log u) 中的快速傅里叶变换来解决您的问题。有关此方法或上述方法之一的更多详细信息，请参阅上面的链接。

由于您的问题取决于解决 3SUM，这是一个众所周知的问题，因此您不太可能找到比上述 3SUM 的知名解决方案具有更好运行时间的解决方案。

要查找 1 个元素：

您可以进行简单的线性搜索 (O(n))。

要查找 2 个元素：

这可以通过简单地检查 O(n ² ) 中 2 个元素的每个组合来解决（你不需要做更复杂的事情，因为 3 个元素的渐近运行时间将导致 O(n ² ) 总时间，不管这个效率如何是）。

也可以使用与上述 3SUM 相同的方法在 O(n) 或 O(n log n) 中求解。

总运行时间：

O(n ² ) 或 O(n + u log u)，取决于用于求解 3SUM 部分的方法。