algorithm - 从两组中各取一个元素

Question

我们有一群人，比如 P1、P2、P3、P4。我们有两套。假设一组是 {1, 2, 3, 4}，另一组是 {A, B, C}。每个人都有一个元素列表，他可以从两个集合中的每一个中选择。当一个人拥有两个集合中的两个元素时，我们说这个人准备好了。我们希望最大限度地增加准备人员的数量。同一元素不能使用两次。像下面的例子:

People: P1, P2, P3, P4
Set1: {1, 2, 3, 4}
Set2: {A, B, C}

P1 can pick from {1, 2} and {B, C}
P2 can pick from {1, 2, 3} and {C}
P3 can pick from {1, 2} and {B, C}
P4 can pick from {1} and {A, B, C}

上述示例的一个可能的解决方案是:


P1 不选
P2选3和C
P3选择2和B
P4 选择 1 和 A

想到分别对每个集合使用贪心，但实际上为了得到最优解，一个集合的解有时不得不对另一集合进行折衷。

编辑:最大流解决方案解决了原始问题。现在，如果每个人在从 {1, 2, 3, 4} 中选择时都有自己的偏好怎么办？例如，P1 比 1 更喜欢 2。当 P1 可以选择 1 或 2 时，他总是会选择 2。

Answer 1

这可以通过计算如下构造的流网络上的最大流来解决:

• 构造源节点Source
• 为第一组#1到#4的元素构造一个节点；将每个节点连接到 Source。
• 为每个人构建一个节点。根据每个人的兼容性列表将每个人连接到节点 #1..#4(即 P1 连接到 #1 和 #2，P2 到 #1，#2 和 #3，等等)
• 为第二组 A..C 的每个元素构造一个节点。根据兼容性列表将每个节点连接到个人节点。
• 构造一个节点Drain，并将每个节点从A..C连接到drain。

所有边和所有顶点的容量均为 1。这是基于您的兼容性列表的示例:

现在运行 several max flow algorithms 之一在此图定义的流网络上。您获得的最大流量提供了最佳分配: