PHPを用いて合計値が極力等しくなるように２分割（個数も均等）

Question

1から1000の範囲でランダムに数字が50個並んでいるとします。
この数字を25個ずつに2グループ作成する場合、2つのグループのグループ間合計値が極力等しくなるようにするためにはどのようなコードを書けばよいでしょうか？

単純な問題ですが、複雑なアルゴリズムが必要な気がします・・・
その場合、2つのグループの合計値がある程度近づくコードでも可です。

以上、ご指導いただければ幸いです。

Comments

[ikuwow]

こちらの質問が他のユーザから「質問の範囲が広すぎる」という評価を受けています
わからない点を明確にし、調査したこと・試したことと共に記入していただくと、回答が得られやすくなります。

Answer 1

コードはあえて記載しません、少し勉強すれば作れるはずなので想像してみてください。

仕分ける対象が10個かつ大小のりんごの重量だったらで考えていきましょう。
まずは10個のりんごの重量を量ります。
次に10個のりんごの平均重量を出します。

ここまでは誰が考えても一瞬でたどり着けるでしょう。
ここからがエンジニアとしての腕の見せどころです。

一番確実なパターンは、無造作に10個の中から5個を取り出す事を全パターンで行い、
平均重量と完全に一致すればそこで計算終了です、
一致しなければ全パターン行った結果、最も平均重量に近いパターンを覚えておき提出すれば良いのです。

「組み合わせパターン PHP」等でググればおｋ

---

今回はたかが50個中25個なんで全パターンゴリ押しでも大した時間がかかりませんが、
見ないでも良い分は見ないことにしましょう。
分かりやすいように10個からの調査を継続します。

まずはりんご10個重量が小さい順に並べ替えます（PHP ソート等でぐぐってください）

◆：選択 ◇：選択しない

←小 大→
◆◆◆◆◆◇◇◇◇◇
◆◆◆◆◇◆◇◇◇◇
◆◆◆◆◇◇◆◇◇◇
◆◆◆◆◇◇◇◆◇◇
◆◆◆◆◇◇◇◇◆◇
◆◆◆◆◇◇◇◇◇◆
◆◆◆◇◆◇◇◇◇◆
◆◆◆◇◇◆◇◇◇◆
～～～～中略～～～～
◆◇◇◇◇◇◆◆◆◆

これらの選択の仕方ならば下のパターンの方が合計重量が重い事が保証される…
つまりソート済みであることが保証されます。
ならば二分探索で高速に評価出来るので利用しましょう。
10個の内、最も左のものを選択したパターンは21通りですので、最高5回程度の評価で最もプラマイ0に近い値が得られます。

次のパターン（17通り）
◇◆◆◆◆◆◇◇◇◇
◇◆◆◆◆◇◆◇◇◇
◇◆◆◆◆◇◇◆◇◇
～～～～中略～～～～
◇◆◇◇◇◇◆◆◆◆

先ほどのような調子で評価していきましょう。

後はこれの繰り返しなんで、50個中25個を調べるアルゴリズムも同じ組み方すれば
100回程度の評価で回答が出るんじゃないですかね？
5000個中2500個あたりになってくると総当りが不可能になってくるので、この手法を使う事をオススメします。

Answer 2

①ランダムな数値50個
②ソートされた数値50個
③大きい値から順に、逆側の配列の合計値よりも小さいなら追加していく。

こんな方法を考えてみたけど何かがおかしい気がする。はてさて