Недавно я столкнулся с реальной проблемой, которую я могу переформулировать в виде следующей алгоритмической задачи:
Задача:
данный набор из N человек, у каждого из которых есть определенная сумма денег, и набор из M предметов, каждый из которых имеет определенную стоимость, возможно ли продать все предметы?
Каждый предмет должен быть куплен не более чем одним человеком, каждый человек может купить несколько предметов так, чтобы их стоимость не превышала сумму денег, которой он располагает.
Мое предпринятое решение:
Я думал о построении сети и поиске максимального потока, подобного этому:
- Сделать двудольный граф с вершинами в одной части, соответствующими людям , а в другой части - к предметам.
- Соединить людей с источником S и установить граничные мощности на деньги, которые есть у людей.
- Соединить предметы со стоком T и установить граничные мощности со стоимостью предметов.
– Соедините каждого человека с предметами, которые он может купить, и установите предельные возможности в соответствии со стоимостью предмета.
В случае, если каждое ребро в максимальном потоке, найденном в этой сети, либо пусто, либо полностью насыщено, проблема будет решена путем поиска, насыщены ли все ребра, идущие к T, и если мы хотим знать, кто должен купить какой предмет, мы будем смотреть на края между левой и правой частями.
Однако проблема в том, что результирующий поток может содержать частично заполненные ребра (имеется в виду, что человек частично заплатил за какой-то товар), и этот случай я не могу исключить.
