贪心最大流

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 个家庭来扩展其部分分配。我们编辑已知解以恢复归纳假设。

虽然我们仍然可以找到一个 table T1 贪婪已经让第 k 个家庭成员就座，但已知的解决方案没有。如果 T1 处的已知解决方案中有 space，请从 table 中移动第 k 个家庭成员，其中贪婪有 none。否则，已知解决方案的家庭成员不在 k 最大的家庭中，就座于 T1。由于该家庭小于第 k 大家庭，因此第 k 大家庭成员占据 table T2，而较小的家庭则没有。交换这些成员。

Answer 2

很容易举出这样的座位根本不可能的例子，所以假设问题是可以解决的，这里是解决问题的伪代码：

Sort each family i by a(i) in decreasing order
Add each table j to a max-heap with b(j) as the key

For each family i from the sorted list:
    Pop a(i) tables from max-heap
    Add one member of i to each table
    Add each table j back into the max-heap with b(j) = b(j) - 1

让n = a(1) + a(2) + ... + a(p)（即总人数）

假设最大堆使用二叉堆，时间复杂度为：

排序家庭：O(plog(p))
正在初始化表的最大堆：O(qlog(q))
所有弹出和推送 to/from 最大堆：O(nlog(q))

总时间复杂度为 O(plog(p) + qlog(q) + nlog(q))，其中 O(nlog(q)) 可能占主导地位。

由于我们处理的是整数，如果我们对最大堆使用一维桶系统，使得 c 是最大值 b(j)，那么我们最终只会得到 O(n + c)（假设最大堆操作占主导地位），这可能更快。

最后，请为 David 的回答投赞成票，因为证明是必需的，而且非常棒。

贪心最大流

Greedy Maximum Flow

algorithm

greedy

max-flow