ビンの最大荷重を最小限に抑える方法について

-1

ビンがnビンとmボールがあります。ボールは異なる重さで、ボールはiの重量はw_iです。ボールをx<nビンに割り当てるアルゴリズムがあるので、ビンの最大負荷が最小限に抑えられます。ビンの最大荷重を最小限に抑える方法について

出典

2011-06-28 Richard

...そう...？ –

この質問はhttp://cstheory.stackexchange.comに属しますが、そこにはすでにたくさんの質問がありますので、私はそれを移行しません。代わりに、私は話題にはならないようにして閉じ、そのサイトに既にある質問をレビューし、あなたの質問に答えが出てくるかどうかを確認してください。検索リンクは次のとおりです。http://cstheory.stackexchange.com/search?q=packing –

これはmultiprocessor scheduling problemに相当します。これはNP完全です。換言すれば、アルゴリズムは存在するが、それらは非常に遅い。

出典

2011-06-28 14:42:09

Aasmundはこれを取得します。 – Colin

これは偽装されたハッシュ関数の質問です。すなわち、あなたは最適なハッシュ関数を探しています。このページをチェックしてください - http://en.wikipedia.org/wiki/Hash_function

通常、あなたはw_iでXORできるランダムなキーが必要です。その後、結果のmod nを使ってビン番号を取得してください。

注：1ビンあたりのボール数を意味するために最大限の負荷をかけました。ハッシュは各ビンの重量を最小限に抑えたい場合はうまくいきません。

出典

2011-06-28 14:42:24 Colin

彼は（最適なハッシュ関数が与えるであろう）_numberのボールの均一な分布には興味がありませんが、_weight_の均等な分布です。 –

私はあなたが間違っていると信じて、Aasmundは正しい答えを持っています。この問題がハッシングにどのように関連しているのかは分かりませんが、結果として得られるマッピングがハッシュ関数として表現できるという事実を除いては（しかしそれはあまり面白くなく面白いです）。 –

btw - 私たちは問題を実際には解決していませんが、np完了問題に対する最適な解決方法はかなり簡単です。ビンへのボールの可能な組み合わせをすべて実行して、どれが最良の結果をもたらすかを確認してください:-) – Colin

ビンの最大荷重を最小限に抑える方法について

答えて

関連する問題