1

合計が等しくなるように、配列を2つの空でない互いに素なサブセットに分割しようとしています。 

eg. A = {1,2,3,6,88,55,29}  
one possible answer = 1+2+3  and 6

バランスの取れたパーティションの問題に関する mit チュートリアルを読みましたが、制約が異なります。セット A 全体を考慮する必要はありません (つまり、A1 U A2 が A になる必要はありません)。また、別の問題は N の制限です。それぞれ最大 100 の個別の要素 (<= 100 ) があります。私の問題に関連するこの 投稿
も読み ましたが、何も得られませんでした。 

My present Algo -- 
p[1][a[0]] = 1
for i = 2 to n
   for j = 0 to n*n
     if( p[i][j] >= 2) stop

            p[i][j] += j - a[i] > 0 ? ( p[i-1][j] + p[i-1][j-a[i]] ):0
            p[i][j] += j == a[i] ? 1:0
            p[i][j] += j < a[i] ? p[i-1][j]:0

説明 ：

Search for sum j at position i. If we got count at position j >=2 means 
there are more than two possibilities for summing up to j.

HEREは私によるサンプル作業コードです

この方法ではばらばらなセットを処理できないことはわかっていますが、他のアプローチを見つけることはできません。

私はDynamic Progの学習段階にあります。と、やや難しいと思います。誰かが私の現在のアルゴリズムのエラーを見つけるのを手伝ってくれますか?

4

1 に答える 1

1

あなたのコードはすべてのサブセットを網羅していないようです。サイズのセットのPower Setnには2^n-1空でない要素があるため、これがアルゴリズムの複雑さの下限であると思います。SOに関するこの他の質問に関連するように、サブセットを列挙する適切な方法を見つける必要があります

一般に、サブセットの生成は要素を 1 つずつ追加することによって行われます。これにより、動的計画法を使用する場合、1 回の加算で個々のセットの合計を計算できます。実際、 が{1,2,3,6}あり、値を に保存する場合は、 の合計を見つけるため12に追加するだけです。88{1,2,3,6,88}

基本的な DP 以外に、さらなる最適化を見つけることができます。たとえば、テストする場合

 {88} > {1,2,3,6,29}

{1,2,3,6,29}まず、 のサブセット(より小さい合計)をテストする必要はありません{88}。同時に、88 を含むセットを でテストする必要はありません{1,2,3,6,29}。これは、常に大きくなるためです...大きなセットから小さなセットへの再帰を使用する必要があります。

于 2012-06-10T07:58:12.323 に答える