假设有N组人，M张 table 。我们知道每个组的大小和每个表的容量。我们如何将人与 table 进行匹配，使得同一组的两个人不会坐在同一张 table 上？
贪心法对这个问题有效吗？ (贪婪方法的工作原理如下:对于每个表，尝试用来自不同组的人“填充”它)。
最佳答案
假设组和表的大小可能不相等，我认为所描述的贪婪方法行不通(至少在没有附加规范的情况下是行不通的)。假设您有一张 2 T1 的 table 和一张 3 T2 的 table ，以及 3 个组 {A1}、{B1,B2} 和 {C1,C2}。如果我按照你的算法，T1 将收到 {A1,B1}，现在你只剩下 T2 和 {B2,C1,C2}，这是行不通的。然而，存在解决方案 T1 {B1,C1}，T2 {A1,B2,C2}。
我怀疑以下贪婪方法有效:从最大的一组开始，将每个组分配给每张 table 的那个组中的一个人，选择空闲座位最多的第一张 table 。
关于algorithm - 贪婪的方法在这里有效吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8771592/