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

Question

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

问题:是否有一种有效的算法来枚举该组的k-组合,以便组合I在组合J之前,如果I中元素的总和小于或等于J中元素的总和？

---

显然,可以简单地枚举组合并根据它们的总和对它们进行排序.但是,如果集合很大,那么所有组合的粗略枚举,更不用说排序,将是不可行的.如果我只对获得按总和排序的第一个m <<选择(n,k)组合感兴趣,是否有可能在宇宙热死之前获得它们？

Answer 1

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

如果有这样的算法(让它是A),那么我们可以多项式求解子集和问题:

1. 跑A
2. 进行二分查找以找到最接近所需数字的子集.

请注意,步骤1以多项式(假设)运行,第2步运行O(log(2^n)) = O(n).

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

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