3

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

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

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

如果我们总是以贪婪的方式坐在较大的群体前面。复杂度为 O(10^6)。

所以我的问题是：

1）这个问题的贪婪方法有效吗？

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

4

2 回答 2

3

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

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

虽然我们仍然可以，但找到一张T1贪婪的k家庭成员坐下但已知解决方案没有的桌子。如果已知解决方案中有空间，则将第T1一个k家庭成员从贪婪的没有空间的表中移出。否则，已知解决方案的家庭成员不在k最大的家庭中T1。由于该家庭小于k第 th 大家庭，因此第kth 大家庭成员占据了T2较小家庭没有的桌子。交换这些成员。

于 2016-07-28T17:00:16.147 回答
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)（假设最大堆操作占主导地位），这可能更快。

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

于 2016-07-29T01:00:08.397 回答