贪心最大流

Question

Dining Problem：
几个家庭一起出去吃饭。为了增加他们之间的社交互动，他们希望坐在不同桌子上，以便同一个家庭的两个成员不会坐在同一张桌子上。假设这顿晚餐有p个家庭，第i个家庭有a(i)个成员。同时，假设有q张桌子可用，第j张桌子的座位容量为b(j)。

问题是： 我们可以在桌子上最多坐多少人？

编辑： 该问题可以通过创建图并运行最大流算法来解决。但是，如果使用Dinic算法对2 * 10 ^ 3个顶点进行计算，则全局复杂度为O(10 ^ 6 * 10 ^ 6) = O(10 ^ 12)。

如果我们总是先坐较大的团体，以贪心的方式处理，则复杂度为O(10 ^ 6)。

所以我的问题是：

1）在这个问题中，贪心方法有效吗？

2）解决此问题的最佳算法是什么？

- Manuel

---

这可能是一个更适合于计算机科学SE的问题。 - jackzellweger

Answer 1

是的，先贪心地安排最大的家庭是一个正确的解决方案。我们只需要证明，在安排完下一个最大的家庭后，还有一种方法可以正确地安排剩下的家庭。

假设问题是可解的。我们通过归纳证明，当贪心算法安排了$k$个最大的家庭时，存在一个解决方案。基础情况$k = 0$显然成立，因为要证明的假设是存在解决方案。归纳地，假设存在一个解决方案，扩展了前$k-1$个家庭的贪心部分分配。现在，贪心算法通过安排第$k$个家庭来扩展其部分分配。我们编辑已知的解决方案，以恢复归纳假设。

当我们仍然能够时，在贪心算法安排了第$k$个家庭成员但已知解决方案没有安排时，找到一个表格$T1$。如果已知解决方案中的$T1$有空间，则从贪心算法没有任何家庭成员的桌子上移动第$k$个家庭成员。否则，已知的解决方案在$T1$处有一个不属于前$k$个最大的家庭中的成员。由于该家庭比第$k$大的家庭更小，第$k$大的家庭成员占据了一个较小的家庭没有的桌子$T2$。交换这两个成员即可。

- David Eisenstat

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))
• 所有弹出和推入最大堆的操作：O(nlog(q))

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

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

最后，请投票支持David的答案，因为需要证明并且非常好。

- wookie919