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))可能占主导地位。

由于我们正在处理整数,如果我们对最大堆使用一维桶系统,使得最大值为cb(j)那么我们最终将只得到O(n + c)(假设最大堆操作占主导地位),这可能更快。

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

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