2

値のリスト (例: 10、15、20、30、70)、値 N (例: 3) および値 S (例: 100) を指定して、以下を満たすサブセットを見つけます。

  1. サブセットの長さ >= N
  2. サブセットの合計 >= S

サブセットの合計も可能な限り最小にする必要があります (残りの値の合計は可能な限り最大にする必要があります) (たとえば、結果サブセットは (15,20,70) ではなく (10,20,70) にする必要があり、これも 1 を満たします。および 2.)。

いくつかの問題と解決策 (ナップザックの問題、ビンのパッキングの問題など) を調べていましたが、適用できるものは見つかりませんでした。インターネット上の同様の問題も、何らかの理由で適切ではありませんでした (サブセット内の要素の数が修正されたなど)。

誰かが私を正しい方向に向けることができますか? 考えられるすべての組み合わせを使い果たす以外に解決策はありますか?

編集 - ルビーコードに実装した作業アルゴリズム、さらに最適化できると思います:

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。指定されたセットから特定の合計が可能かどうかを追跡する (つまり、true/false を格納する) ことに加えて、次を満たすために長さも格納する必要があります。

  1. サブセットの長さ >= N

もしそうならsum of subset = S、それは上記の問題とまったく同じです。条件についてsum of subset >= Sは、Wikiページに記載されているように、配列を構築するときにこの条件をテストできると思います。

于 2012-07-25T13:44:05.297 に答える