Алгоритм распространения

Question

У вас есть список «людей» Lp и еще один список «продуктов питания» Lf.

Каждый элемент в Lp хочет получить один или несколько элементов в Lf, но может получить только один.

Как должен быть алгоритм для определения того, какой элемент в Lf дает каждому элементу в Lp (не нужно распространять все Lf и не предоставлять всем Lp). Вы пытаетесь максимизировать количество Lp, которому присвоен Lf, который он хотел.

Answer 1

Это может быть решена путем моделирования задачи в виде графика и решения для maximum flow следующим образом:

1. Рассмотрим каждому человеку узел в графе; назовем эти p-узлы.
2. Рассмотрите каждую пищу другого узла в том же графе; назовем эти f-узлы.
3. Если человек a любит пищу b, добавить ребро между P_A и f_b. Делайте это для каждой пищи, которую любой любит. Каждый из этих ребер будет иметь емкость 1.
4. Создайте исходный узел I, который подключается к каждому p-узлу. Поскольку каждый человек может есть не более 1 пищи, края от I до каждого p-узла также должны иметь емкость 1.
5. Создайте узел-приемник O, который соединяется с каждым f-узлом. Поскольку каждая пища может быть съедена не более чем на 1 человека, эти края также должны иметь емкость 1.
6. Запустите алгоритм Edmonds-Karp (или любой другой алгоритм максимального потока); и посмотрите на выход. Ответы на проблему - ребра из p-узлов на f-узлы, используемые результирующей сетью с максимальным потоком.

Обратите внимание, что, изменяя емкость ребер, вы можете разместить варианты описания проблемы.