餐饮问题:
几个家庭一起出去吃饭。为了增加他们的社交互动,他们喜欢坐在桌子旁,这样同一个家庭的两个成员就不会坐在同一张桌子上。假设晚餐队伍有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)解决这个问题的最佳算法是什么?