贪婪的最大流量

Question

该用餐问题：
几个家庭一起出去吃晚饭。为了增加他们的社交互动，他们想坐在餐桌旁，以便同一个家庭中没有两个成员在同一个桌子上。假设晚餐队伍有p家庭，并且i家庭拥有a(i)成员。此外，假设有q表格可用，并且j表格的座位容量为b(j)。

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

编辑： 这个问题可以解决，创建一个图形和运行最大流量算法。但如果我们有2 * 10^3顶点的Dinic算法，则全局复杂度为O（10^6 * 10^6）= O（10^12）。

如果我们只是以一种贪婪的方式总是先坐在较大的群体上。复杂度是O（10^6）。

所以我的问题是：

1）是否在这个问题上的工作贪婪的方法呢？

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

Answer 1

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

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)（假设最大堆操作占主导地位），这也许更快。

最后，请提高大卫的答案，因为证明是必需的，真棒。

Answer 2

是的，首先贪婪地坐在最大的家庭是一个正确的解决方案。我们只需要证明，在我们坐下一个最大的家庭之后，就可以正确地安置其余的家庭。

假设一个实例是可解的。我们通过归纳证明，在贪婪算法占据最大家族之后存在一个解决方案。基础k = 0是显而易见的，因为要证明的假设是存在解决方案。归纳地说，假设存在一个扩展第一个k - 1系列贪婪的部分分配的解决方案。现在，贪婪通过坐上k这个家庭来扩展其部分任务。我们编辑已知的解决方案来恢复归纳假设。

尽管我们仍然可以找到一张表T1，其中贪婪已经坐了k家庭成员，但已知的解决方案没有。如果在T1的已知解决方案中存在空间，请将一个k的家庭成员从贪婪没有的表中移出。否则，已知解决方案的家庭成员不在k大家庭中，坐落在T1。由于该家庭小于第k次大，所以第012大家庭成员占据表T2，小家庭没有。交换这些成员。