私はこの問題を前に見つけましたが、バランスのとれた問題です。プログラムは、サイズnの整数の配列を取ります。プログラムは、この整数の配列を2つの等しい部分に分割し、各半分の整数の和が等しいかどうかを判定します。バランスの取れた小石の問題
ex。 1 2 3 8 10 4
プログラムは、各
14で半分ずつに分割することができることを意味し、trueを返します、ここで私は、これは組み合わせ/順列と懸念している知っていると私は非常に本当にないんだけどそれらに良い。私はブルートフォースの方法を考えることしかできませんでした。これは他の方法でも解決できますか？より効率的なアルゴリズムかもしれない？
ステップバイステップの解決策が非常に役立ちます。ありがとうございました
これは容易と同等であることが分かるPartition ProblemではありませんおよびKnapsack Problem。それはNP完全であり、あなたはすべての組み合わせの完全なリストよりもはるかに良くできないと考えられています。
すべての可能な方法を簡単に確認できます。各要素について、左半分または右半分のいずれかになります。
お返事ありがとう！あなたはロック – maru
最初のリンクから： "サブセット和問題の擬似多項式時間動的プログラミング解法はパーティション問題にも適用され、与えられた整数のサイズが制限されているときの多項式時間で正確な答えが得られます。しかし一般的に、入力の数字は入力サイズで指数関数的になる可能性があり、この方法は実現できない可能性があります。 –
thisの私の答えを見てください。あなたの問題は必然的につながっています。あなたは数字で達成できる合計を見つけなければなりません。合計した場合：total_sum/2を達成することができ、あなたは解決策を見つけました:)
はちょうどそれにいくつかの本当に短いの考えを与える：
http://en.wikipedia.org/wiki/Partition_problem – DhruvPathak
フィンガーツリーのデータ構造が私の頭に浮かびます。おそらくそれを使って段階的な解決策を得るための方法があります。 – ony