分发算法

Question

你有一个“人”列表 Lp 和另一个“食物”列表 Lf。

Lp 中的每个元素都想要 Lf 中的一个或多个元素，但只能接收一个。

算法应该如何决定 Lf 中的哪个元素给 Lp 中的每个元素(不需要分配所有 Lf 也不需要提供给所有 Lp)。您正在尝试最大化分配了所需 Lf 的 Lp 的数量。

Answer 1

这可以通过将问题建模为图形并求解 maximum flow 来解决。如下:

1. 将每个人视为图中的一个节点；让我们称这些为 p 节点。
2. 将每种食物视为同一图中的另一个节点；让我们称这些为 f 节点。
3. 如果人 a 喜欢食物 b，则在 p_a 和 f_b 之间添加一条边。对任何人喜欢的每种食物都这样做。每条边的容量都是 1。
4. 创建一个连接到每个 p 节点的源节点 I。由于每个人最多只能吃 1 种食物，因此从 I 到每个 p 节点的边的容量也应为 1。
5. 创建一个连接到每个 f 节点的汇节点 O。由于每种食物最多可供 1 人食用，因此这些边的容量也应为 1。
6. 运行 Edmonds-Karp算法(或任何其他最大流算法)；并查看输出。生成的最大流网络使用的从 p 节点到 f 节点的边就是问题的答案。

请注意，通过更改边的容量，您可以适应问题陈述的变化。