algorithm - 如何按总和枚举集合的所有k组合？

Question

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

问题：是否有一种有效的算法来枚举该集合的 k 组合，以便组合 I 先于组合 J 且当且仅当 I 中的元素之和小于或等于 J 中的元素之和？

---

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

Answer 1

没有以这种方式枚举集合的多项式算法（除非P=NP）。

如果有这样的算法（假设为 A），那么我们可以多项式地解决子集和问题：

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- 计算它可能是可行的。