2

私は以前にこの問題に遭遇しました、それはバランスの問題です。プログラムは、サイズnの整数の配列を受け取ります。次に、プログラムは、この整数の配列を2つの等しい部分に分割できるかどうかを判断し、各半分の整数の合計が等しくなります。

元。1 2 3 8 10 4

ここで、プログラムはtrueを返します。つまり、それぞれ14個ずつで2つに分割できます。

私はこれが組み合わせ/順列に関係していることを知っています、そして私はそれらがあまり得意ではありません。私は力ずくの方法を考えることができました。これは他の方法で解決できますか？より効率的なアルゴリズムかもしれませんか？

ステップバイステップのソリューションは非常に役立ちます。どうもありがとうございます

4

3 に答える 3

2

ちょっと考えてみてください。

  • この問題は、小石の総重量のちょうど半分の重さの小石のサブセットを見つけることと同じです。
  • 最も重い小石の重量が小石の総重量の半分を超える場合、解決策はありません。
于 2011-02-09T09:17:45.273 に答える
1

これは、サブセット和問題やナップサック問題と同等であることがすぐにわかるパーティション問題です。これはNP完全であり、すべての組み合わせの完全なリストよりもはるかに優れているとは考えられません。

考えられるすべての方法を簡単に確認できます。各要素について、左半分または右半分のいずれかにあります。

于 2011-02-09T09:34:58.863 に答える
0

この問題に対する私の答えを見てください。あなたの問題は本質的に関連しています。あなたはあなたが数字で達成できる合計を見つけなければなりません。合計total_sum / 2が達成できる場合は、解決策が見つかりました:)

于 2011-02-09T08:21:55.307 に答える