wvo*_*voq 2 algorithm combinatorics
假设我有一组有限的大小为n的数值.
问题:是否有一种有效的算法来枚举该组的k-组合,以便组合I在组合J之前,如果I中元素的总和小于或等于J中元素的总和？
显然,可以简单地枚举组合并根据它们的总和对它们进行排序.但是,如果集合很大,那么所有组合的粗略枚举,更不用说排序,将是不可行的.如果我只对获得按总和排序的第一个m <<选择(n,k)组合感兴趣,是否有可能在宇宙热死之前获得它们？
ami*_*mit 5
没有用于以这种方式枚举集合的多项式算法(除非P = NP).
如果有这样的算法(让它是A),那么我们可以多项式求解子集和问题:
请注意,步骤1以多项式(假设)运行,第2步运行O(log(2^n)) = O(n).
O(log(2^n)) = O(n)
结论:由于子集和问题是NP完全,有效地解决这个问题将证明P = NP - 因此没有已知的多项式解决问题.
编辑:即使问题是NP-Hard,m也可以O(n+2^m)通过选择最小m元素,从这些m元素生成所有子集- 并选择其中的最小元素来获得"最小" 子集m.因此,对于相当小的值m- 计算它可能是可行的.
m
O(n+2^m)
归档时间：
13 年，2 月 前
查看次数：
572 次
最近记录：