给定一组人（类似于）：
[p1,p2,p3]
[p2,p3]
[p1]
[p1]
从每组中选择 1 个，尽量减少任何一个人被选中的最大次数。
对于上述集合，必须选择给定人员的最大次数为 2。
我正在努力为此找到一个算法。我不认为它可以用贪心算法来完成，更多地沿着动态编程解决方案的思路思考。
关于如何去做的任何提示？或者你们中的任何人都知道任何关于这些东西的好网站，我可以看看吗？
问问题
346 次
1 回答
5
这既不是动态的，也不是贪婪的。我们先来看一个不同的问题——是否可以通过最多选择每个人一次来完成？
你有 P 个人和 S 套。创建一个带有 S+P 顶点的图，表示集合和人。当 pi 是 si 的一个元素时，person pi 和 set si 之间有一条边。这是一个二分图，然后您的问题的决策版本等效于测试该图中的最大基数匹配是否具有大小 S。
如该页所述，这个问题可以通过使用最大流量算法来解决（注意：如果你不知道我在说什么，那么现在就花点时间阅读它，因为你不会理解其余的否则）：首先创建一个超级源，添加一条连接到所有容量为 1 的人的边（表示每个人只能使用一次），然后创建一个超级接收器并添加连接每个集合到容量为该接收器的边1（表示每组只能使用一次）并在源和接收器之间运行合适的最大流算法。
现在，让我们考虑一个稍微不同的问题：是否可以通过最多选择每个人k次来完成？
如果你注意了上一段的注释，你应该知道答案了：只要改变离开超级源的边的容量，以表明在这种情况下每个人都可能被多次使用。
因此，您现在有一个算法来解决最多选择k次人的决策问题。不难看出，如果你可以用k来做，那么你也可以用任何大于k的值来做，也就是说，它是一个单调函数。因此，您可以对问题的决策版本运行二进制搜索，寻找仍然有效的最小 k。
注意：您还可以通过顺序测试 k 的每个值来摆脱二分搜索，并增加上次运行中获得的残差网络，而不是从头开始。但是，我决定解释二进制搜索版本，因为它在概念上更简单。
于 2012-10-04T00:33:39.843 回答