講堂での席の割り当て

Question

私はインタビューの質問に遭遇しました：

講堂にはイベントがあり、講堂の所要量はNxMです。 予約された人のチケットのすべてのグループとすべてのチケットが予約されていますので、グループ分けの最小数など、すべての人に座席番号を割り当てる必要があります。

基本的に2-D配列が与えられており、いくつかのサイズのグループがあります（異なるグループは異なるサイズかもしれません）.Arrayは最小数のグループ分割で完全に埋められる必要があります。

ブルートフォース再帰的なアプローチは、次のとおりです。最初のグループ、次に2番目のグループなどを配置します。最小の分割で配置を見つけるためにこの配置を行います。

私が見つけた1つの効率的な解決策は、サブセットサム問題を使用していました。 https://en.wikipedia.org/wiki/Subset_sum_problem

この問題を解決するためにサブセットサム問題をどのように使用できるか理解できませんでした。 どうすればこの問題に近づくことができますか。私はコードを探していません。ちょうど擬似コードまたはアルゴリズムで十分です。

Answer 1

まず、「グループ分割」とは、グループの一部がある行にあり、残りが別の行にあることを意味します。ある行の座席数がNであり、異なるグループのサイズを含む集合が与えられている場合、Nに合計する部分集合を見つける必要があります。そのような部分集合が見つかった場合、その行は中断することなく塗りつぶされます任意のグループ。そのようなサブセットが見つからない場合は、少なくとも1つのグループを解除する必要があります。次に、複数の戦略があります。

1）2行にまたがるグループを選択できます。このグループは、残りの中で最大のものでも、最小のものでも、ランダムに選ぶこともできます。このグループが決まると、再帰的に満たす必要がある空のシート数がN未満の2行があります。

2）戦略は、2 * Nに合計する部分集合を見つけることができます。見つかった場合、1つのグループが分割されます。見つからなければ、2つのグループ分割などで合計3 * Nのサブセットを見つけます。グループ分割の最大数は、M行の場合、M-1になります。

劇場のM個の行を埋めるために1）または2）を続けます。