algorithm - 贪心最大流

Question

就餐问题:
几个家庭一起出去吃饭。为了增加他们的社交互动，他们喜欢坐在餐 table 旁，这样同一家庭的两个成员就不会坐在同一张 table 上。假设晚餐队伍有 p 个家庭，第 i 个家庭有 a(i) 个成员。此外，假设有 q 个 table 可用，并且第 j 个 table 的座位数为 b(j)。

问题是:我们最多可以坐在 table 上多少人？

编辑:这个问题可以通过创建一个图并运行一个最大流算法来解决。但是如果我们用 Dinic 算法有 2*10^3 个顶点，全局复杂度是 O(10^6*10^6) = O(10^12)。

如果我们总是以贪婪的方式让较大的组排在第一位。复杂度为 O(10^6)。

所以我的问题是:

1) 这个问题中的贪心方法是否有效？

2) 解决这个问题的最佳算法是什么？

Answer 1

是的，贪婪地让最大的家庭优先入座是一个正确的解决方案。我们只需要证明，在我们为下一个最大的家庭安排座位后，还有一种方法可以正确安排剩余的家庭。

假设一个实例是可解的。我们通过归纳法证明，贪心算法将k个最大的家族落座后，存在解。 k = 0 的基础很明显，因为要证明的假设是存在解。归纳地，假设存在一个解决方案，它扩展了对前 k - 1 族的贪心部分分配。现在，贪婪通过安置第 k 族来扩展它的部分分配。我们编辑已知的解决方案以恢复归纳假设。

虽然我们仍然可以找到一张 T1 表，但贪心算法已经让第 k 位家庭成员就座，但已知的解决方案没有。如果在 T1 的已知解决方案中有空间，则从 greedy 没有的表中移动第 k 族成员。否则，已知解决方案的家庭成员不在 k 最大的家庭中，坐在 T1 上。由于该家族小于第 k 大家族，因此第 k 大家族成员占据了表 T2，而较小的家族则没有。交换这些成员。