假设有N组人和M张桌子。我们知道每个组的大小和每个表的容量。我们如何将人与桌子匹配，以使同一组的两个人不会坐在同一张桌子上？
贪婪的方法是否适用于这个问题？（贪婪方法的工作原理如下：为每张桌子尝试“填充”来自不同群体的人）。
问问题
444 次
3 回答
4
假设组和表的大小可能不相等，我认为所描述的贪婪方法行不通（至少在没有额外规范的情况下不是这样）。假设您有一个包含 2 个 T1 的表和一个包含 3 个 T2 的表，以及 3 个组 {A1}、{B1,B2} 和 {C1,C2}。如果我遵循您的算法，T1 将收到 {A1,B1}，现在您只剩下 T2 和 {B2,C1,C2} 这不起作用。然而有一个解 T1 {B1,C1}, T2 {A1,B2,C2}。
我怀疑以下贪婪的方法会奏效：从最大的一组开始，每个组分配一个人，每张桌子分配一个人，挑选第一张空位最多的桌子。
于 2012-01-07T17:43:59.877 回答
2
马蒂亚斯：
我怀疑以下贪婪的方法会奏效：从最大的一组开始，每个组分配一个人，每张桌子分配一个人，挑选第一张空位最多的桌子。
的确。tkleczek 论点的一个小变化证明了这一点。
假设有一个解决方案。我们必须证明算法在这种情况下找到了解决方案。
如果组数为 0，则这是空洞的。
对于归纳步骤，我们必须证明如果有任何解决方案，那么最大组的一个成员坐在每个（最大组的大小）最大表中。
条件 L：对于所有表对 (T1,T2)，如果 T1 < T2 并且最大组的一个成员坐在 T1 上，那么最大组的另一个成员坐在 T2 上。
让 S1 成为一个解决方案。如果 S1 满足 L 我们就完成了。否则，有一对 (T1,T2) 的表 T1 < T2 使得最大组的成员坐在 T1 但最大组的成员没有坐在 T2。由于 T2 > T1，有一个组有一个成员坐在 T2，但在 T1 没有成员（或者在 T2 有一个空闲位置）。所以这两个可以交换座位（或者最大组的成员可以移动到 T2 的空闲位置），我们得到一个解决方案 S2，其中违反 L 的桌子对更少。由于只有有限数量的桌子，经过有限多步我们找到了一个满足 L 的解 Sk。
归纳假设：对于所有 N 个组的星座和所有 M 个表，如果有解，算法就会找到解。
现在考虑存在解决方案的 (N+1) 个组和 M 个表的星座。综上所述，还有一种方案是按照算法放置最大组的成员。这样放置。这将问题简化为 N 个组和 M' 表的可解星座，由算法根据归纳假设来解决。
于 2012-01-08T03:30:52.837 回答
1
以下贪心方法有效：
重复以下步骤，直到没有座位为止：
- 选择最大的组和最大的表
- 将所选组中的一个人匹配到所选表
- 将组大小和表大小减少 1。
证明：
我们只需要证明在执行一步之后我们仍然可以达到最优解。
让我们称最大群体中的任何成员为酷人。假设有一个不同的最佳解决方案，其中没有帅哥坐在最大的桌子旁。让我们在这个解决方案中选择坐在最大桌子上的任何人，称其为跛脚的人。他必须属于规模不大于酷组的组。所以还有另一张桌子上坐着一个很酷的人，但没有跛脚的人。我们可以安全地交换跛脚和酷家伙的座位，这也导致了最佳解决方案。
于 2012-01-07T20:14:44.637 回答