已知子集大小和数组为连续范围的子集求和问题

Question

已知子集大小和数组为连续范围的子集求和问题

3

我正在尝试找到一种快速解决子集和问题的方法，并进行了一些修改。我知道我需要获取目标数字的确切子集大小，并且我也知道输入数组是从1到2000的范围。我的问题是，如果在知道这些条件的情况下有没有改进基本子集和问题解决方案的方法，使其更快，因为常规解决方案太慢了。基本上，唯一变化的部分就是希望得到的目标总和。

最好能够返回所有可能的满足给定大小且总和等于目标值的子集，如果可能的话，而不会使程序运行过慢。如果能提供一个Python或类似语言的示例代码，那就太好了。

我已经尝试了许多解决基本子集和问题的方法，但由于输入数组太大而无法执行。

- Fanfer123

当你说输入数组是“从1到2000的范围”时，你的意思是什么？你的意思是它是[1, 2, 3, ... 2000]吗？ - Matt Timmermans

@MattTimmermans 是的，那就是我的意思。 - Fanfer123

你是被要求找到一个解决方案还是计算可能的解决方案数量？ - rici

@rici，在我的问题中，我确实说过，如果可能的话，我更希望它返回所有可能的子集，这些子集的大小相同且总和等于目标值，而不会使程序变得太慢。 - Fanfer123

@Fanfer123：在组合问题中，计算解的数量和生成所有解是非常不同的。生成指数级数量的解必然很慢（对于解的数量而言），但通常可以非常高效地计算它们的数量。 - rici

2个回答

0

首先找到解决这个问题的连续子数组，或者尽可能接近连续的子数组。如果宽度为奇数，则其中心将是目标/宽度，如果宽度为偶数，则其中心将是(target-1)/width，(target+1)/width。

找到中心后，在两侧添加相同数量的邻居，直到达到所需的宽度。在没有连续解决方案的情况下，数组的最右元素需要向右移动更远。

Ruby code:

def f(target, width)
  arr = []

  # put in center of array
  if width % 2 == 0
    arr.append target / width
    arr.append target / width + 1
  else
    arr.append target/width
  end
  
  # repeatedly prepend next smallest integer
  # and append next largest integer
  while arr.length < width
    arr.unshift(arr[0] - 1)
    arr.append(arr[-1] + 1)
  end
  
  # increase the last element of the array to match
  # the target sum. This is only necessary if there is no
  # contiguous solution. Because of integer division, 
  # where we need to adjust it will always be to increase
  # the sum of the array.
  arr[-1] += target - arr.sum
  
  return arr
end

Example run:
> f(12342, 7)
=> [1760, 1761, 1762, 1763, 1764, 1765, 1767]

请注意，此代码不执行任何确认解存在于范围（1,2000）内的工作，但您的代码应该执行此操作。

到目前为止，速度很快，但是找到解决方案的所有子集将会很慢，因为有很多。您可以通过将元素向左和向右推动来找到它们。成对出现。

最终答案将是i的总和：（将元素向左推动累积i个空格的方法数）（将元素向右推动累积i个空格的方法数）。

举个简单的例子：对于目标13，宽度为3，我们从[3,4,6]开始。

pushes: arrays
0: [3, 4, 6]
1: [2, 4, 7], [2, 5, 6]
2: [1, 4, 8], [1, 5, 7], [2, 3, 8]
3: [1, 3, 9]
4: [1, 2, 10]

...然后我们就完成了。这将会有大量的操作，我认为当数组的宽度是范围宽度的一半，并且初始数组位于范围中心时，操作数量会达到峰值。

- Dave

在我的算法的最后一步中，我们将数组的最后一个元素增加k。你可能更喜欢将最后的k个元素增加1。这可以确保数组的最后一个元素在您的范围内，如果在您的范围内存在任何解决方案的话。 - Dave

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DrosvarG · Accepted Answer

知道子集的大小是非常强大的信息，因为您不必迭代子集大小。

给定N个子集大小，您可以：

对输入数组的前N个元素求和（大小为N的第一个子集）
通过减去子数组的第一个元素并添加其旁边的元素来迭代，这相当于查看下一个子数组
如果总和等于目标数字，则返回子数组

无论初始数组内容如何，这应该在时间上是O(input array size)，在内存上是O(1)。可能存在使用初始数组的范围属性的更优解决方案。

以下是C++示例：

void subsetSum(std::vector<int>() array, int subArraySize, int targetNumber)
{
    int sum = 0;
    for (int i = 0; i < subArraySize; ++i) // Initial sum
    {
        sum += array[i];
    }
    for (int i = subArraySize; i < array.size(), ++i)
    {
        sum -= array[subArraySize-i];
        sum += array[i];
        if (sum == targetNumber)
            std::cout << subArraySize-i; // this print the starting position of the subarray
    }
}