学生にシャペロンを割り当てるための堅牢なアルゴリズム

Question

サイズA、B、C、Dの4つのグループの学生と合計k個のシャペロンを与えられた場合、シャペロンをほぼ等しい割合でシャペロンに割り当てるためのアルゴリズムを考案する。

シャペロンの数は正の整数でなければならないので、k * A/N、k * B/N、k * C/N、k * D/Nのシャペロンだけを与えることはできません。そして、ちょうど回り込むことはできません。なぜなら、あなたはシャペロンの正しい数を得ることができないからです。だから私の考えは、小数部分を捨て、整数部分を各グループに与えることです。次にシャペロンに残っているものがいくつかあるかもしれませんが、最大で3つなので、残りの部分が最も大きいグループにそれらを渡してください。

それから、面接官はこれに問題があると指摘しました。別のシャペロンを加えると、kをk + 1に増やすと、グループの1つがシャペロンを失うことがあります。彼女は私に例を挙げましたが、私はそれを覚えていません。

誰もこの問題を回避するアルゴリズムを考え出すことができますか？

Answer 1

解決しようとしている問題は、一般に 割り当て問題または投票割り当て問題として知られています。これは、 の問題と同じです。米国内の座席数を の各州の代表者に割り当てると問題になります。

（ハミルトンの メソッドまたは最大の残りの部分の方法として知られている）あなたのアプローチを持っているために失敗した堅牢性の問題が Alabama Paradoxとして知られています。 ウィキペディアの記事「アラバマのパラドックスは、1880年に発見された。 は、席数を増やすとアラバマのシェアが8から7に減少することがわかった。

歴史的に、少なくとも4つの異なる方法が、米国で使用されています： ジェファーソンの方法、ハミルトンの方法、ウェブスターの方法及びこれらの後者の方法の背後にある1941年

考え方は以下のとおりであるので、使用 現在Huntington-Hill's method を。 D = N/k、 を総人口を座席数/シャペロン数で割ったものにします。その後 は、座席の正確な数、すなわち

ラウンド（G_1/D）+ラウンド（G_2/D）+ ... +ラウンド（G_m/Dにつながりますd = Dをしましょう、と丸めk_i = round(G_i/d) までdを変更します）= k

キャッチは機能roundの仕組みにあります。 Websterのアプローチ は、通常の意味でのラウンドをとります。弱く.5上に上がり、厳密には.5 の下になります。これは、算術平均を使用するのと非常によく似ています。 Huntington-Hill法は、代わりに幾何平均 を使用するという考え方に基づいています。これらの方法の素敵な要約があります here。注釈 これらすべての除数アルゴリズムには、 クォータルールに違反するという欠点があります。状態は少なくとも floor(G_m/D)の代理人を取得する保証はありません。

Cut The Knotには の記事があります。 の履歴、方程式、および楽しいアプレットがあります。

Answer 2

サイズA、B、CおよびDの4つのグループの学生、および合計k個のシャペロンが与えられた場合、シャペロンをほぼ等しい割合でシャペロンに割り当てるためのアルゴリズムを考案する。ここで

非常に単純に疑問を解決するアルゴリズムです：

1. は、グループごとに0シャペロンの配分を開始します。いずれかのグループに生徒がいない場合、そのグループにはシャペロンが割り当てられないので、そのグループを廃棄します。

2. 割り当てられたシャペロンの総数がkに等しい場合、完了する。

3. 1つのシャペロンを1つのグループに割り当てる。シャペロンを受け取るグループは、学生比率ごとにシャペロンが最も低いグループです。ネクタイの場合、学生比率が最も低いシャペロンの中で最も生徒の多いグループを選択します。それでもタイがある場合は、選択したグループの中からアルファベット順にグループを選択します。

4. ゴー2.

をステップそれは明確な決定論的な割り当てを行います。割合は、許容値とほぼ同じになります。 kを増やしても、すべてのグループの割り当てが減少することはありません。追加の反復が発生するだけで、グループの割り当てが反復されないためです。

同じサイズの2つのグループが異なるシャペロン数を持つ可能性はありますが、問題を修正してkを変更できるようにすることはできません。同じサイズの2つのグループは、1より大きい割り当てによって異なる。

表現を状態に割り当てる他の答えのアルゴリズムはすべて、不必要に複雑であり、計算ステップの数を最小限に抑えるように設計されている増分割り当てではなく数値計算を実行することによって実行されます。私が与えたアルゴリズムは、コンピュータ上で実行すると非常に簡単です。