1

マルチセットが別のマルチセットのサブセット和の和集合であるかどうかを検証するアルゴリズムを見つけたいのですが、一人で数時間苦労して失敗しました。

詳細は次のとおりです。

マルチセット A: 正の整数セット

マルチセット B: 正の整数セット (A 以下、理由は後でわかります)

アルゴリズム関数: B のすべての数値について、A の 1 つの数値または数値の合計が一致するかどうかを検証します。A の各数字は 1 回しか使用できず、A のすべての数字を使用する必要があります。B のすべての数値が一致する必要があります。

これを明確にする例: multiset A = {1, 3, 4, 4, 6} , B = {5, 6, 7} とします。

5 は 1 と 4 の合計、6 は 6、7 は 3 と 4 の合計であるため、アルゴリズムは「TRUE」を出力します。 B がチェックされます。

しかし、A = {2, 6, 8}、B = {7, 9} の場合、アルゴリズムは「FALSE」を出力しますが、2+6+8 = 7+9 ですが、B の数値は A の数値の合計ではありません。 .

いくつかのメモ:

1 既知の条件、A の数値の合計は B の数値の合計に等しい。

2 例が示すように、特定の数が複数回表示される場合があります。

3 マルチセットの各数値は 1 回しか使用できないため、1 つの解で 3 を使用すると (7 を取得するために)、別の解で再度使用することはできません。数字の 4 は 2 回現れるので、2 つのソリューションで使用できます。

4 1 つの数に対して複数の解が考えられます (7 は 1 と 6、または 3 と 4 のように) が、一部 (7 は 1 と 6 のように) は検証プロセスで間違っている可能性があります。

5 マルチセット A は大きくなく、最大で 30 要素です

私は最善を尽くしますが、私の解決策は常にマルチセット A と B のすべての条件をカバーすることはできません。これに対する解決策は明らかに私を超えていると思いました。

だから、私はあなたの賢い人々の助けが本当に必要です。私を助けてください。どんな答えでも大歓迎です！

4

1 に答える 1

2

これは NP 完全問題です (「部分和問題」への還元は非常に簡単です)。したがって、この問題に対する効率的な解決策はありません。

ここでそれを解決するさまざまな方法を見ることができます: http://en.wikipedia.org/wiki/Subset_sum_problem

単純なアルゴリズム:

naiveAlg(A,B) :
  for each partition P of A such that |P| = |B| do :
    for each element E in P do :
      calculate the sum of E numbers and store in E'
    if E' is equal to B return true
  return false
于 2012-08-06T17:20:45.567 に答える