ができる2つの「コンテナ」に番号を配布し、n個の数字があると仮定合計

Question

のそれらの差を最小限にすることは、我々は2つのあり、コンテナAとBがあり、私の次の4つの数字15,20,10,25

を持っていると言います仕事は、各コンテナ内の数字の合計が最小の差を持つように数字を配布することです。上記の例で

私は方法を考える10+ 25だから差= 0

を有するべきで、Aは、15 + 20及びBを有するべきです。それはうまくいくように思えますが、私は理由を知らない。

番号リストを降順で最初に並べ替えます。各ラウンドでは、最大数を から取り出し、コンテナに入れる合計を少なくします。

Btw、それはDPで解決できますか？ THX

Answer 1

1. 実際には、あなたの方法は、常に動作しません。そのことについて2,4,4,5,5と考えてください。あなたの方法による結果は(5,4,2)(5,4)になりますが、最良の答えは(5,5)(4,4,2)です。

   チュートリアルやコード：http://www.cs.cornell.edu/~wdtseng/icpc/notes/dp3.pdf
   実践：

2. はい、それは動的計画法 .Hereでを解決することができますが、いくつかの有用なリンクですhttp://people.csail.mit.edu/bdean/6.046/dp/（当時Balanced Partitionをクリック）

3. さらに、問題の規模が大きければ（500万数字など）、あなたはあまりにも巨大な行列を必要とするDPを使いたくないでしょう。このような場合は、モンテカルロアルゴリズムの種類使用する：無作為に2つの群に

   1. 除算n個の数字を（またはあなたが好きならば、この段階で、あなたの方法を使用します）。
      
   2. 
      各グループから1つの番号を選択すると（これらの2つの数値をスワップすると合計の差が小さくなります）スワップします。
      
   3. "スワップが長時間発生しない"まで手順2を繰り返します。

   あなたは、このメソッドは、常に最高の答えを出し仕事ができる期待したくないが、それは合理的な時間とメモリ内非常に大規模なで、この問題を解決するために、私が知っている唯一の方法です。