古いプログラミング コンテストのサンプル問題を解いていました。この質問では、バーテンダーが何人いて、どのレシピを知っているかを入力します。各カクテルの作成には 1 分かかります。すべてのバーテンダーを使用して、注文が 5 分以内に終了できるかどうかを計算する必要があります。
この問題を解決する鍵は、できるだけ効率的にカクテルを割り当てることです。そして、それが私が立ち往生しているところです.私の現在のアルゴリズムは、他のレシピを最も知らないバーテンダーに注文を与えます. しかしもちろん、これはまだ 100% 正しいわけではありません。この「バーテンダーの問題」を解決する正しい方向に向けて（またはGoogleにアルゴリズム名を付けて）くれる人はいますか？
これは、フロー ネットワークで解決できます。
ソースからシンクへの最大フローを計算します。注文が履行されない場合、解決策はありません。
これは頂点カラーリングの問題です。これは、非常によく研究されているレジスタ割り当て問題とまったく同じです。http://en.wikipedia.org/wiki/Register_allocationを参照してください。これは、頂点の色付けに類似したセット カバーの問題と考えることもできます。
もちろん、ここで実際の色を見つける必要はありません。カーディナリティが 5 以下かどうかを判断する必要があるだけです。バーテンダー グラフを 5 色以下で色付けできる場合、答えは「はい」です。 .polymtl.ca/pub/sites/lagrapheur/docs/en/documents/NotesChap7.pdf .
さて、これを理解するために、グラフの「彩色数」または「彩色指数」と呼ばれるものは NP 困難です。実際、グラフの彩色数を見つけるためのアルゴリズムについて SO に問い合わせた人がいますが、残念ながら多くの回答は得られませんでした。グラフの彩色数のアルゴリズムを参照してください。
Web を見回すだけで、色付けを行うためのコード リソースがいくつか見つかりました。この問題を解決できるものはSMALLKと呼ばれます。SMALLK は 8 つまでの塗り絵を見つけることができます。この問題では 5 つしか必要ないため、このパッケージで解決できます。
これは、大学のマッチング問題の変形です。飲み物は学生で、バーテンダーは大学です。これは、安定した結婚の問題の一般化であり、より役立つ可能性があります。