2

質問は言う、

サイズ n の配列が与えられた場合、配列を出力/分割して、合計が N になるサブセットにする必要があります。

For E,g, 
    I/p  arr{2,4,5,7}, n=4, N(sum) = 7(given)
    O/p = {2,5}, {7}

URL Dynamic Programming3で同様の問題/説明を見ました

そして、私はpdfに次のクエリを持っています:-

  1. 論理はサブセットが存在するかどうかしか分からないので、合計が N になるサブセットをどのように見つけることができるでしょうか?
  2. また、質問を少し変えると、同じイデオロギーを使用して平均が等しい 2 つの部分集合を見つけることができますか?

誰でもこの動的プログラミングの問題に光を当てることができます.. :)

前もって感謝します..

4

3 に答える 3

1

再帰的に処理を試みることができます:

SORTED 配列 X={x1 ... xn} xi !=0 と整数 N が与えられます。

最初に、たった 1 つの要素で「作られた」すべての可能性を見つけます。

ここで、N=xp の場合、すべての xi st i>=p を削除します

次に、 2つの要素で作成されたすべての可能性を見つけます。

{ (x1,x2) .... (xp-2,xp-1)}

合計で並べ替え、すべての合計 >=N を削除すると、次のルールが適用されます: xi+xj >= N

3 番目の 3 つの要素: 上記のルールを尊重するすべてのパーツを作成します。そして同上ステップ2など...

例：

X={1,2,4,7,9,10} N=9

step one:
{9}
X'={1,2,4,7,9}

step 2: cannot chose 9 and 10
X={(1,2) (1,4) (2,4) (1,7) (2,7) (4,7)}
{2,7}
X'={(1,2) (1,4) (2,4) (1,7)}

step 3: 4 and 2 cannot go with 7:
X={(1,2,4)}
no sol

{9} {2,7} are the only solutions

これにより、実行した比較の総数 (2^n = 2^6=64) が減少します: 12 回の比較

それが役に立てば幸い

于 2011-06-27T13:50:31.563 に答える
1

残念ながら、これは非常に難しい問題です。目標値に合計する単一のサブセットが存在するかどうかを判断することさえNP-Completeです。

問題がより制限されている場合は、適切なアルゴリズムを見つけることができる場合があります。例えば：

  • サブセットは連続している必要がありますか?
  • K 値を超えるサブセットを無視できますか?
  • 配列の値は正であることが保証されていますか?
  • 配列の値が異なることが保証されていますか? 他の値と少なくとも一定の係数で異なることはどうですか?
  • 最小値と最大値の差に制限はありますか?
于 2011-06-27T16:57:44.290 に答える
0

提案されたアルゴリズムは、単一ビットの情報のみを一時配列T[N]に格納します。つまり、到達可能かどうかです。[N]明らかに、そこに到達するために使用される値など、より多くの情報を各 index に格納できますC[i]。(これは、PDF の「無制限のコピーの取り扱い」の章のバリエーションです)

于 2011-06-27T13:59:05.007 に答える