私はしばしば大規模な入門プログラミング クラス (400 人から 600 人の学生) を教えています。試験の時期になると、全員が試験を受けられるようにクラスを別々の部屋に分割する必要があることがよくあります。
物事を論理的に単純にするために、私は通常クラスを姓で分けます。たとえば、姓が A ～ H の生徒を 1 つの部屋に、姓が I ～ L の生徒を 2 番目の部屋に、M ～ S を 3 番目の部屋に、T ～ Z を 4 番目の部屋に送ることができます。
これを行う際の課題は、部屋の定員が大きく異なることが多く、全員が収まるようにクラスを分割する方法を見つけるのが難しい場合があることです. たとえば、姓の分布が (簡単にするために) 次のようになっているとします。
- Aで始まる姓：25
- Bで始まる姓：150
- Cで始まる姓: 200
- Dで始まる姓：50
収容人数が 350、50、および 50 の部屋があるとします。部屋の割り当てを見つけるための貪欲なアルゴリズムは、部屋を収容人数の降順に並べ替えてから、その順序で部屋を埋めようとすることかもしれません。残念ながら、これは常に機能するとは限りません。たとえば、この場合、正しいオプションは、姓 A をサイズ 50 の部屋に入れ、姓 B ～ C をサイズ 350 の部屋に入れ、姓 D をサイズ 50 の別の部屋に入れることです。姓 A と B を 350 人の部屋に入れ、他の全員の席を見つけることができません。
この問題は、部屋の順序付けのすべての可能な順列を試してから、各順序付けで欲張りアルゴリズムを実行するだけで簡単に解決できます。これにより、機能する割り当てが見つかるか、存在しないことが報告されます。ただし、部屋の数が 10 から 20 の間であり、すべての順列をチェックするのは現実的ではない可能性があるため、これを行うためのより効率的な方法があるかどうか疑問に思っています。
要約すると、正式な問題ステートメントは次のとおりです。
クラス内の学生の姓の頻度ヒストグラムと、部屋とその定員のリストが表示されます。あなたの目標は、各部屋に連続した文字のブロックが割り当てられ、その容量を超えないように、姓の最初の文字で生徒を分割することです。
これには効率的なアルゴリズムがありますか、または妥当な部屋サイズに対して効率的な少なくとも 1 つのアルゴリズムはありますか?
編集：多くの人が連続した状態について尋ねてきました. ルールは
- 各部屋には、最大でも連続した文字のブロックを割り当てる必要があります。
- 2 つ以上の部屋に文字を割り当てることはできません。
たとえば、A - E、H - N、および P - Z を同じ部屋に入れることはできません。また、A ～ C を 1 つの部屋に、B ～ D を別の部屋に配置することもできません。
ありがとう！