algorithm - 如何通过和枚举集合的所有 k 组合？

Question

假设我有一组大小为 n 的有限数值。

问题:是否有一种有效的算法来枚举该集合的 k 个组合，以便当 I 中元素的总和小于或等于组合 I 的总和时，组合 I 优先于组合 J J 中的元素？

---

显然，可以简单地枚举组合并根据它们的总和对它们进行排序。然而，如果集合很大，则无法对所有组合进行暴力枚举，更不用说排序了。如果我只对获得按总和排名的前 m << select(n,k) 组合感兴趣，是否有可能在宇宙热寂之前获得它们？

Answer 1

没有多项式算法可以用这种方式枚举集合(除非 P=NP )。

如果有这样一个算法(设其为A)，那么我们可以解决subset sum problem多项式:

1. 运行A
2. 进行二分搜索以查找总和最接近所需数字的子集。

请注意，第 1 步按多项式运行(假设)，第 2 步按 O(log(2^n)) = O(n) 运行。

结论:由于子集和问题是 NP-Complete ，有效地解决这个问题将证明 P=NP - 因此这个问题没有已知的多项式解。

---

编辑:即使问题是 NP-Hard，获取“最小”m 子集也可以在 O(n+2^m) 上完成 通过选择最小的 m 元素，从这些 m 元素生成所有子集 - 并选择其中最小的 m 元素。因此，对于相当小的 m 值 - 计算它可能是可行的。