7
2つの部分の平均が等しいように、どのように2つの部分に分割するのですか？各パーティションには、配列内で連続していない要素が含まれている場合があります。 私が考えることができる唯一のアルゴリズムは指数関数的です。2つの部分の平均が等しいように、どのように2つの部分に分割するのですか？
A
答えて
12
sum-subset problemにもこの問題を減らすことができます - cached here。ここにその考えがあります。
Aを配列とします。 を計算します.Nの長さはAです。 kについては、1からN-1までは、T_k = S * k/Nとなります。 T_kが整数の場合は、の合計がkのAのサブセットを見つけます。あなたがこれを行うことができれば、あなたは完了です。 kでこれを実行できない場合は、そのようなパーティショニングは存在しません。
これは、このアプローチの背後にある数学です。サイズがxのXとサイズyのYがx+y = Nであると言うと、Aというパーティションが2つの部分が同じ平均を持つようになっているとします。そして、あなたは
sum(X)/x = sum(Y)/y = (sum(A)-sum(X))/(N-x)
を持っている必要があり、配列は整数を含んでいるのでそう代数のビットは、左側が整数である、
sum(X) = sum(A) * x/N
を与えるので、右側も同様でなければなりません。これは、T_k = S * k/Nが整数でなければならないという制約を引き起こす。唯一の残りの部分は、サイズkのサブセットの合計としてT_kを実現することです。
+0
です。少し考えても、あなたの証明がOPの問題のサブセット和をどのように減らすかはまだ分かりません。 – soulcheck
+0
私は、あなたが根本的に、OPの問題に答えることができるサブセットの合計に答えていることを証明しました。それ以外の方法ではありません。 – soulcheck
+0
@soulcheck私はまだ彼らが本当に同等かどうか熟考しています。答えは[私がちょうど尋ねたこの質問]（http://stackoverflow.com/questions/8916539/sum-subset-with-a-fixed-subset-size）になっていると思います。 – PengOne
正直、これは宿題に関する質問ですか？ –
何を試しましたか？それは動作しましたか？サンプルの入力と出力を持つテストケースがありますか？ –
これはインタビューの質問のように聞こえるが、簡単なことではない。 – BrokenGlass