贪婪最大流量

Question

用餐问题:
几家人一起出去吃饭。为了增加他们的社会交往，他们愿意坐在桌子上，这样同一家庭的两个成员就不会在同一张桌子上。假设晚餐特遣队有p家庭，而i家庭有a(i)成员。另外，假设有q桌可用，并且j第1桌的座位容量为b(j)。

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

编辑：创建一个图并运行最大流算法可以解决这个问题。但如果我们用Dinic算法有2*10^3个顶点，则全局复杂度为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)（即总人数）

假设max-heap使用二进制堆，则时间复杂度为：

• 排序族:O(plog(p))
• 初始化最大表堆:O(qlog(q))
• 所有弹出和从max-heap推送：O(nlog(q))

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

由于我们处理的是整数，如果我们对max-heap使用一个1D bucket系统，使得c是最大的B(j)，那么我们将只得到O(n+c)（假设max-heap操作占主导地位），这可能更快。

最后，请投票给大卫的答案，因为证明是必需的，而且是很棒的。