2

给定一个值列表（例如 10、15、20、30、70）、值 N（例如 3）和 S（例如 100），找到满足的子集：

  1. 子集长度 >= N
  2. 子集的总和 >= S

子集的总和也应该是最小的（剩余值的总和应该是最大的）（例如结果子集应该是（10,20,70），而不是也满足 1 的（15,20,70）。和 2.)。

我正在研究一些问题和解决方案（背包问题、装箱问题……），但没有发现它们适用。由于某些原因，互联网上的类似问题也不适合（例如子集中的元素数量是固定的）。

有人可以指出我正确的方向吗？除了用尽所有可能的组合之外，还有其他解决方案吗？

编辑 - 我在 ruby​​ 代码中实现的工作算法，我想它可以进一步优化：

def find_subset_with_sum_and_length_threshold(vals, min_nr, min_sum)
    sum_map = {}
    vals.sort.each do |v|
      sum_map.keys.sort.each do |k|
        addends = sum_map[k] + [v]
        if (addends.length >= min_nr && k+v >= min_sum)
          return addends
        else
          sum_map[k+v] = addends
        end
      end
      sum_map[v] = [v] if sum_map[v].nil?
    end
  end
4

2 回答 2

1

这与0-1背包问题没有太大区别。

Zero-initialize a matrix with S+U rows and N columns(U is the largest list value)
Zero-initialize a bit array A with S+U elements
For each value (v) in the list:
  For each j<S:
    If M[N-1,j] != 0 and M[N-1, j + v] == 0:
      M[N-1, j + v] = v
      A[j + v] = true
  For i=N-2 .. 0:
    For each j<S:
      If M[i,j] != 0 and M[i+1, j + v] == 0:
        M[i+1, j + v] = v
  M[0,v] = v
Find first nonzero element in M[N-1,S..S+U]
Reconstruct other elements of the subset by subtracting found value from its\
  index and using the result as index in preceding column of the matrix\
  (or in the last column, depending on the corresponding bit in 'A').

时间复杂度为 O(L*N*S)，其中 L 是列表的长度，N 和 S 有限制。

空间复杂度为 O(L*N)。

Zero-initialize an integer array A with S+U elements
i=0
For each value (v) in the list:
  For each j<S:
    If A[j] != 0 and A[j + v] < A[j] + 1:
      A[j + v] = A[j] + 1
      V[i,j + v] = v
      P[i,j + v] = I[j]
      I[j + v] = i
  If A[v] == 0:
    A[v] = 1
    I[v] = i
  ++i
Find first element in A[S..S+U] with value not less than N
Reconstruct elements of the subset using matrices V and P.

时间复杂度为 O(L*S)，其中 L 是列表的长度，S 是给定的限制。

空间复杂度为 O(L*S)。

也最小化子集大小的算法：

Zero-initialize a boolean matrix with S+U rows and N columns\
  (U is the largest list value)
Zero-initialize an integer array A with S+U elements
i=0
For each value (v) in the list:
  For each j<S:
    If A[j] != 0 and (A[j + v] == 0) || (A[j + v] > A[j] + 1)):
      A[j + v] = A[j] + 1
      V[i,N-1,j + v] = v
      P[i,N-1,j + v] = (I[j,N-1],N-1)
      I[j+v,N-1] = i
  For k=N-2 .. 0:
    For each j<S:
      If M[k,j] and not M[k+1, j + v]:
        M[k+1, j + v] = true
        V[i,k+1,j + v] = v
        P[i,k+1,j + v] = (I[j,k],k)
        I[j+v,k+1] = i
  For each j<S:
    If M[N-1, j]:
      A[j] = N-1
  M[0,v] = true
  I[v,0] = i
  ++i
Find first nonzero element in A[N-1,S..S+U] (or the first element with smallest\
  value or any other element that suits both minimization criteria)
Reconstruct elements of the subset using matrices V and P.

时间复杂度为 O(L*N*S)，其中 L 是列表的长度，N 和 S 有限制。

空间复杂度为 O(L*N*S)。

于 2012-07-25T12:03:37.780 回答
0

这是子集和问题的一个轻微变化。看节Pseudo-polynomial time dynamic programming solution。除了跟踪给定集合中的特定总和是否可能（即存储真/假）之外，您还需要存储长度以满足：

  1. 子集长度 >= N

如果sum of subset = S那么它与上述问题完全相似。对于sum of subset >= S条件，我想您可以在构建 Wiki 页面中提到的数组时测试此条件。

于 2012-07-25T13:44:05.297 回答