给定一个包含n个整数的集合,将该集合划分为两个大小均为n/2的子集,以使两个子集的和之差尽可能小。如果n是偶数,则两个子集的大小必须严格为n/2;如果n是奇数,则一个子集的大小必须为(n-1)/2,另一个子集的大小必须为(n+1)/2。
例如,给定集合{3, 4, 5, -3, 100, 1, 89, 54, 23, 20},集合的大小为10。这个集合的输出应该是{4, 100, 1, 23, 20}和{3, 5, -3, 89, 54}。两个输出子集的大小都为5,两个子集中元素的总和相同(148和148)。
另一个例子是当n为奇数时。给定集合{23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}。输出子集应该是{45, -34, 12, 98, -1}和{23, 0, -99, 4, 189, 4}。两个子集中元素的总和分别为120和121。
经过多次搜索,我发现这个问题是NP-Hard问题。因此,不可能有一个多项式时间复杂度的解法。不过,我考虑到以下方法:
1. 将第一个元素初始化为第一个子集。 2. 将第二个元素初始化为第二个子集。 3. 根据哪个子集大小更小,哪个子集中的总和缺乏,我会插入下一个元素。
我猜这样可以实现线性时间复杂度。
然而,这里提供的解决办法太过复杂:http://www.geeksforgeeks.org/tug-of-war/。我无法理解它。因此,我想问一下,我的方法是否正确?考虑到这是一个NP-Hard问题,我认为应该可以吧?如果不行,能否有人简要地解释一下链接上的代码如何工作呢?谢谢!
例如,给定集合{3, 4, 5, -3, 100, 1, 89, 54, 23, 20},集合的大小为10。这个集合的输出应该是{4, 100, 1, 23, 20}和{3, 5, -3, 89, 54}。两个输出子集的大小都为5,两个子集中元素的总和相同(148和148)。
另一个例子是当n为奇数时。给定集合{23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}。输出子集应该是{45, -34, 12, 98, -1}和{23, 0, -99, 4, 189, 4}。两个子集中元素的总和分别为120和121。
经过多次搜索,我发现这个问题是NP-Hard问题。因此,不可能有一个多项式时间复杂度的解法。不过,我考虑到以下方法:
1. 将第一个元素初始化为第一个子集。 2. 将第二个元素初始化为第二个子集。 3. 根据哪个子集大小更小,哪个子集中的总和缺乏,我会插入下一个元素。
我猜这样可以实现线性时间复杂度。
然而,这里提供的解决办法太过复杂:http://www.geeksforgeeks.org/tug-of-war/。我无法理解它。因此,我想问一下,我的方法是否正确?考虑到这是一个NP-Hard问题,我认为应该可以吧?如果不行,能否有人简要地解释一下链接上的代码如何工作呢?谢谢!
D(x,i)
是什么以及true和false代表什么的描述? - John LuiD(x,i)
表示您可以使用前i
个元素从中获取总和为x
的子集。这意味着,D(SUM/2,n)
意味着列表中存在一个大小为SUM/2
的子集,其中包含任何元素。 - amit*n
乘数到复杂度中,使其变为O(SUM*n^2)
而不是O(SUM*n)
。 - amit