algorithm - 最优选择选举算法

Question

给定一组人(类似于):

[p1,p2,p3]
[p2,p3]
[p1]
[p1]

从每组中选择 1 个，尽量减少任何一个人被选中的最大次数。

对于上面的集合，给定的人必须被选中的最大次数是 2。

我正在努力为此寻找算法。我不认为它可以用贪心算法来完成，更多的是沿着动态规划解决方案的思路来思考。

关于如何进行此操作的任何提示？或者你们中有人知道关于这些东西的任何好的网站我可以看看吗？

Answer 1

这既不是动态的也不是贪婪的。让我们先来看一个不同的问题 -- 是否可以通过最多选择每个人一次来完成？

你有 P 人和 S 组。创建一个带有 S+P 顶点的图，表示集合和人。当且仅当 pi 是 si 的一个元素时，人 pi 和集合 si 之间存在一条边。这是 bipartite graph并且您的问题的决策版本相当于测试 maximum cardinality matching 是否该图中的大小为 S。

如该页面所述，可以使用 maximum flow 解决此问题。算法(注意:如果你不知道我在说什么，那么现在花点时间阅读它，否则你将无法理解其余部分):首先创建一个 super 源，添加一个链接到它的边缘所有容量为 1 的人(表示每个人只能使用一次)，然后创建一个 super 接收器并添加将每个集合连接到容量为 1 的接收器的边(表示每个集合只能使用一次)并运行一个合适的源汇之间的最大流算法。

现在，让我们考虑一个稍微不同的问题:是否可以通过最多选择每个人 k 次来完成？

如果你注意了最后一段的注释，你应该知道答案:只需更改离开 super 源的边缘的容量，以表明在这种情况下每个人可能被使用多次。

因此，您现在有了一个算法来解决最多选择人 k 次的决策问题。很容易看出，如果你可以用k来做，那么你也可以用任何大于k的值来做，也就是说，它是一个单调函数。因此，您可以对问题的决策版本运行二分搜索，寻找仍然有效的最小 k 值。

注意:您还可以通过依次测试 k 的每个值并增加上次运行中获得的残差网络而不是从头开始来摆脱二分搜索。但是，我决定解释二进制搜索版本，因为它在概念上更简单。