鉴于一堆人(类似于):
[p1,p2,p3]
[p2,p3]
[p1]
[p1]
从每组中选择1,尝试最小化选择任何一个人的最大次数.
对于上面的集合,必须选择给定人员的最大次数是2.
我很难为此获得算法.我不认为可以用贪婪的算法来完成,更多地考虑动态编程解决方案.
关于如何解决这个问题的任何提示？或者你们是否知道任何有关这些东西的好网站我可以看看？
这既不动态也不贪婪.让我们首先看一个不同的问题 - 可以通过最多选择一个人一次来完成吗？
你有P人和S组.使用S + P顶点创建一个图形,表示集合和人员.如果pi是si的元素,则在人pi和set si之间存在边缘.这是一个二分图,然后您的问题的决策版本等同于测试该图中的最大基数匹配是否具有S的大小.
正如该页面上详述的那样,这个问题可以通过使用最大流算法来解决(注意:如果你不知道我在说什么,那么现在就花时间阅读它,因为你不会理解其余的否则):首先创建一个超级源,添加一个边缘将其链接到容量为1的所有人(表示每个人只能使用一次),然后创建一个超级接收器并添加链接每个集合到容器的容量1(表示每组只能使用一次)并在源和接收器之间运行合适的最大流算法.
现在,让我们考虑一个稍微不同的问题:是否可以通过最多k次选择每个人来完成？
如果您注意到最后一段中的注释,您应该知道答案:只需更改离开超级源的边缘的容量,以指示在这种情况下每个人可能被使用多次.
因此,您现在有一个算法来解决人们最多被选中k次的决策问题.很容易看出,如果你能用k做,那么你也可以用任何大于k的值来做,也就是说,它是一个单调的函数.因此,您可以对问题的决策版本运行二进制搜索,查找仍然有效的最小k值.
注意:您还可以通过按顺序测试k的每个值来消除二进制搜索,并增加在上次运行中获得的剩余网络,而不是从头开始.但是,我决定解释二进制搜索版本,因为它在概念上更简单.