Алгоритм, который представляет собой комбинацию проблемы непрерывного рюкзака и проблемы с упаковкой бинарного размера

Я пытаюсь решить проблему (в php, но язык программирования не имеет значения). У меня есть n число людей, которые заплатили деньги, и у меня есть количество людей, которые собираются заплатить ту же сумму, что и сумма того, что заплатил n человек. Я хочу рассчитать кратчайший маршрут денежных переводов между этими лицами. Можно разделить платежи и выплатить разным лицам. Идеальным является то, что один человек совершает только одну или две транзакции. Может кто-нибудь может указать мне в правильном направлении или помочь мне с этим?

Пример: человек А заплатил 100 долларов США

человек B заплатил $200

человек C заплатил $50

человек D заплатит $24

человек E заплатит $175

человек F заплатит $151

Одним из возможных решений для этого является

человек E платит 100 долларов США человеку,

человек E платит $75 человеку B,

человек F платит $125 человеку B,

человек F платит $26 человеку C

человек D платит 24 доллара США человеку

1 ответ

В теории это может быть обрамлено как проблема оптимизации:

В основном мы собираемся установить набор ограничений, которые перечисляют структуру вашей проблемы, заносят начальные значения и удостоверяются, что мы выделяем все деньги, как вы указали.

Исходные условия:

A_paid = 100
B_paid = 200
C_paid = 50
D_out = 24
E_out = 175
F_out = 151

Сумма выплат не может превышать доступную сумму: (мы определяем D_to_A как переменную, удерживающую сумму, выплачиваемую человеком D лицу A)

D_out >= D_to_A + D_to_B + D_to_C
E_out >= E_to_A + E_to_B + E_to_C
F_out >= F_to_A + F_to_B + F_to_C

Сумма, выплачиваемая каждому человеку, должна быть равна тому, что они уже заплатили:

A_paid = D_to_A + E_to_A + F_to_A
B_paid = D_to_B + E_to_B + F_to_B
C_paid = D_to_C + E_to_C + F_to_C

Если бы мы остановились и решили это как линейную программу, мы найдем любое решение, охватывающее все переменное пространство, но вы хотите минимизировать количество фактических платежей. Мы можем сделать это, минимизируя по всем переменным X_to_Y в соответствии с вышеприведенными ограничениями.

min: D_to_A + D_to_B + D_to_C + ...

Вы можете использовать свою любимую технику оптимизации для решения этой проблемы, есть множество доступных линейных программных решателей, мне нравится lpsolve.

Хотя это решает конкретный пример, вам было легко понять, как его можно расширить до больших проблем, добавив больше переменных... но проблема значительно возрастает по мере добавления людей. Если я правильно помню, проблема с рюкзаком - NP или NP-hard, так что это не неожиданно.

licensed under cc by-sa 3.0 with attribution.