12

コンテナの合計値が可能な限り均等になるように、設定された数のコンテナに数字を均等に分配する方法を知っている人はいますか?

編集:「可能な限り」とは、X個のコンテナに分散されている場合、各コンテナの合計が合計平均にできるだけ近くなることを意味します。

今は単純に数値の配列を並べ替え (降順)、それらの値を知らずにコンテナーに配布します。3 つのコンテナーに分散された 1000、200、20、1000 のセットは、[2000]、[200]、[20] に等しくなります。

私がやりたいことは次のとおりです。

Example

Set of numbers: 10 30 503 23 1 85 355
If I were to distribute these into three containers I would just pick the highest first and then distribute them as I go, like this:
Cont 1 = 503
Cont 2 = 355
Cont 3 = 85 + 30 + 23 + 10 + 1

This will give the best possible distribution that you can get with the values provided.

しかし、これをコードで表現するきちんとした方法を知りません。

アイデア？

4

2 に答える 2

3

大規模なデータセットがあり、オブジェクトのサイズに大きなばらつきがあり、最適なソリューションを見つける必要がある鋳鉄の要件がありますか? もしそうなら、これは現実的ではありません。

しかし、良いニュースは、理論上は NP 完全である多くの問題が、現実の世界では非常に簡単であることです! データポイントの数が比較的少ない場合は、おそらくインテリジェントな (ただし徹底的な) 検索を実行して、グローバルに最適なソリューションを見つけることができます。

また、適切に動作するデータセットがあり、値の分散が非常に小さい場合、すべてのコンテナーを正確に均等に満たすソリューションにすぐに出くわす可能性があります。もしそうなら、これは明らかに可能な限り最良の答えです。これは、非常に大きなデータセットでもうまく機能します。（ここで必要なのは、最後に簡単に整理するために使用できる小さな値がたくさんあるデータセットだと思います。）

だから、あきらめないでください！まず、データを並べ替えて、データ ポイントを最大のものから最小のものまで検討します。各段階で、現在最小のコンテナに次の値を割り当てます。これですべての場合に最適なソリューションが得られるわけではありませんが、実際には非常に合理的です。

ソート1000, 200, 20, 1000すると、 が得られます1000, 1000, 200, 20。このアルゴリズムは、次のようになります。

1000        = 1000
1000        = 1000
200   +20   =  220

これはたまたま最適なソリューションですが、常にそうであるとは限りません。

====

より複雑なアルゴリズムを試してみたい場合は、パーティションの問題を調べてください。

分割問題は NP 完全ですが、疑似多項式時間動的計画法ソリューションがあり、多くの場合、問題を最適または近似的に解決するヒューリスティックがあります。このため、「最も簡単な難しい問題」と呼ばれています。

S1 の要素の合計と S2 の要素の合計の差が最小になるように、マルチセット S を 2 つのサブセット S1、S2 に分割する分割問題の最適化バージョンがあります。

于 2013-10-05T13:29:01.030 に答える