Блог

У меня есть n товаров и m покупателей, прибыль от отправки каждой посылки каждому покупателю, стоимость отправки каждой посылки каждому покупателю. Количество товаров, которые может иметь покупатель, бесконечно. Я хочу максимизировать общий доход и знать, куда отправлять каждый товар.

До сих пор я пробовал проблему максимального потока, когда товары подключаются к суперисточнику с бесконечной емкостью, а покупатели подключаются к суперисточнику с бесконечной емкостью. Между товарами и покупателями я применил соединение от товара к покупателю в качестве прибыли, а от покупателя к товару в качестве затрат (двунаправленное). Затем я применяю алгоритм максимального потока и не получаю правильного ответа.

Что я хочу знать, так это как настроить график таким образом, чтобы применение максимального потока (и, возможно, минимального сокращения) дало бы мне, куда отправлять каждый товар, чтобы максимизировать общий доход