「賞品」/無差別宝くじを均等に配付するアルゴリズム

Question

私の問題：私は「優しい」宝くじプロセスを作りたいと思っています。このアルゴリズムは、可能であれば賞品を均等に配付する。これは、不評の賞品を獲得するために柔軟性があるので、すべての賞品を購入する人々にとって不公平だと考えられますが、賞品はほぼ同じであるとは言い切れません。このアルゴリズムは分散を殺し、ダイスロールを減らして賞品を獲得するのに役立ちます。 （うん、退屈）

私はNあなたは賞を獲得することができました。人Mは、Nごとにチケットを購入できます。

ですから、例えば、ここでチケットを購入した賞品や人々です：

Prize1=[Pete,Kim, Jim] 
Prize2=[Jim, Kim] 
Prize3=[Roger, Kim] 
Prize4=[Jim] 

が4つの賞と4つのユニークな名前がありますので、均等に配布することが可能です。

この例は簡単に解決できるかもしれませんが、15秒後に見つかるはずですが、MとNが増えればそれはさらに悪化します。

私は一般的なアルゴリズムを作ろうとしていますが、それは難しいです。私はいくつかの良いヒントを必要とするか、ソリューションやソリューションへのリンクをより良くする必要があります。

Answer 1

ジョブ割り当てアルゴリズム、またはハンガリーのアルゴリズム、たとえば2部グラフの重み付き完全一致、またはすべてのペアfloyd warshallアルゴリズムを探したいとします。私の考えは、これは二部グラフとして表現できるということです。これは解決しやすい課題ではありません。

Answer 2

理論：あなたはBipartite graphです。あなたはPerfect matchingを見つけなければなりません。グラフに完全一致がある場合：

• | A | = | B |
• グラフを満たすHall condition

完璧なマッチングが存在する場合、あなたはそれを見つけるためにHungarian algorithmを実行することができます。