algorithm - 长度>=N 且总和>=S 的值的子集

Question

给定一个值列表(例如 10、15、20、30、70)、值 N(例如 3)和 S(例如 100)，找到满足以下条件的子集:

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

子集的总和也应该尽可能小(剩余值的总和应该尽可能大)(例如结果子集应该是(10,20,70)，而不是(15,20,70)这也满足 1. 和 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

Answer 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)。