c++ - 与 2,3 和更多整数的子集和相关的想法

Question

我和其他人一样一直在努力解决这个问题，我很确定已经有足够多的帖子来解释这个问题。然而，就完全理解它而言，我想分享我的想法，并从这里所有与子集和问题相关的伟大人士那里获得更有效的解决方案。

我已经在 Internet 上搜索了它，实际上有很多资源，但我真的很愿意重新实现一个算法或找到我自己的算法以便完全理解。

我遇到的关键问题是 效率 考虑到集合大小会很大。 (我没有限制，只是概念上的大)。我尝试实现想法的两个阶段是找到等于给定整数 T 的两个 数字，找到三个 数字并最终 < b>K 个数。我的一些想法；

对于 two 整数部分，我主要是对数组 O(nlogn) 进行排序，并为数组中的每个元素搜索其负值。 (即如果数组元素是 3 搜索 -3)。也许哈希表包含会更好，提供 O(1) 索引元素？

对于三个或更多整数，我发现了一篇很棒的博文；http://www.skorks.com/2011/02/algorithms-a-dropbox-challenge-and-dynamic -编程/。然而，即使是作者自己也表示它不适用于大数。

所以我对 2 和 3 及更多 整数有什么想法可以应用于子集问题。我正在努力建立一种对大输入也有效的动态编程方法。

Answer 1

那个blog post实际上，您链接到的看起来非常棒。毕竟，这是一个 NP 完全问题...

但我敢打赌您可以进一步加快速度。我没有做过任何基准测试，但我猜他对矩阵的使用是他最大的时间消耗。首先，它会为一些非常微不足道的输入占用大量内存(例如:[-1000, 1000] 将需要 2001 列!天哪!)，然后你会浪费大量的周期来扫描每一行寻找 “T”，它们通常会非常稀疏。

所以改为:使用“集合”数据结构。这会将空间和迭代时间保持在最低限度，*但也可以存储值:如果它在集合中，则为 "T"；否则，它是一个 "F"。

希望对您有所帮助!

*:当然，“最小”不一定=“小”。