私は古いプログラミングコンテストのいくつかの質問例を解決していました。この質問では、私たちが持っているバーテンダーの数と、彼らが知っているレシピを入力します。各カクテルを作るのに1分かかるので、すべてのバーテンダーを使用して5分以内に注文を完了できるかどうかを計算する必要があります。私は "バーテンダーアルゴリズム"を見つけようとしています
この問題を解決する鍵は、カクテルをできるだけ効率的に割り当てることです。そして私が立ち往生していること、私の現在のアルゴリズムは、他のレシピが最も少ないバーテンダーに命令を出します。しかし、もちろんこれはまだ100％正確ではありません。誰かが正しい方向に私を指す（または私にGoogleにアルゴリズムの名前を与える）ことができますこの "バーテンダーの問題"を解決する？
これはcollege matching problemの亜種です。飲み物が学生やバーテンダーの場合は、大学です。それはより多くのあなたの役に立つかもしれないstable marriage problemの一般化です。
これは、バーテンダーが5分以内に複数の飲み物を作ることができるので、二部的なマッチングの問題ではありません。 –
各バーテンダーを5回クローニングして1つにすることができます。 –
しかし、バーテンダーは同時に2つの飲み物を作ることはできません – AlexFoxGill
入札がそのカクテル
を作る方法を知っているどのように多くによって配列、順序にカクテルのリストを作成しますため、すなわち （2 * CocktailA、1 * CocktailB、2 * CocktailC、1 * CocktailDのためであります）
CocktailAはCocktailAがCocktailB 3件の入札によって作製することができる（入札者A、B、C）
カクテルCは1回入札可能（入札者A）
CocktailCは
CocktailD入札にジョブを割り当てる、そのリストを
ワーク後方1件の入札（テンダーB）によって作製することができる1件の入札（テンダーA）によって作製することができます。複数の入札者がカクテルを作ることができる場合は、割り当てられたジョブの量が最も少ないものを選んでください。
CocktailD =テンダーB
CocktailC =テンダーA
CocktailC =テンダーA（再び）
CocktailB =テンダーC
CocktailA =テンダーD
CocktailA =テンダーB（再び）
入札A Bさんは両方とも2つのジョブを持っているので、注文は2分かかります。
これは実装が最も簡単な解決策であるようですが、すべてのテストケースで正しい結果が返されたら、試してみましょう。 –
これは動作しません。 「割り当てられたジョブの量が最も少ないものを選ぶ」というルールは、最適なバーテンダーが選択されることを保証しません。 –
私はアルゴリズムが正しいとは思わない - それは検索アルゴリズムのヒューリスティックであるかもしれないが、最初の試みで正しい解決策を常に決めることはできないと思う。 – nhahtdh
これはフローネットワークで解決できます。
ソースからシンクまでのmaximum flowを計算します。注文が未完了のまま残っている場合、解決策はありません。
これは頂点の色付けの問題です。これはまさによく研究されているレジスタ割り付け問題とまったく同じです。 http://en.wikipedia.org/wiki/Register_allocationを参照してください。これは、頂点の色付けに類似した一連の被覆問題と考えることもできます。
もちろん、ここでは実際の色付けを見つける必要はなく、そのカーディナリティが5以下であるかどうかを判断するだけです。バーテンダーグラフを5色以下の色に塗りつぶすことができる場合は、答えは「はい」です。そうでない場合は、「タスク」と「日」と「マシン」の問題を説明するもう1つの良いペーパーがあります。http://www.polymtl.ca/pub/sites/lagrapheur/docs/en/documents/NotesChap7.pdf。
ここで、これを把握するために、グラフの「有彩色数」または「クロマチックインデックス」と呼ばれるものがNP困難です。実際には、誰かがすでにグラフの色数を見つけるアルゴリズムをSOに求めていますが、残念なことに応答の多くを得られませんでした。Algorithm for Chromatic Number of a Graph?
ウェブを見てみると、着色料。この問題を解決できるのはです。 SMALLKは最大8個の着色を見つけることができます。この問題では5個しか必要ないので、このパッケージはそれを行うことができます。
割り当て問題は通常、ハンガリーのアルゴリズムを指します。しかし、私はあなたがここで解決しようとしている問題についてはっきりしていません... – nhahtdh
バーテンダーの問題について聞いたことがない正確な質問を投稿できますか？ Googleは何も出せなかった。 – Halfwarr
私は本当にそれが欲しいなら、私はそれを翻訳する必要があります。 –