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

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

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

человек Б заплатил 200 долларов

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

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

человек Е заплатит 175 долларов

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

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

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

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

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

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

человек D платит 24 доллара человеку C


php optimization algorithm knapsack-problem bin-packing
person jonepatr    schedule 22.08.2010    source источник
comment
Алгоритм оплаты счета? :D Круто!   -  person gaborsch    schedule 10.03.2016

Ответы (1)


arrow_upward
2
arrow_downward

Теоретически это можно сформулировать как задачу оптимизации:

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

Ограничения начальных условий:

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-сложной, так что это не является неожиданным.

person Mark Elliot    schedule 22.08.2010
comment
Ничто в этом не сводит к минимуму количество передач. Я полагаю, что это делает задачу смешанно-целочисленного программирования вместо чисто линейной. - person Ben Voigt; 14.11.2011
comment
@ Бен, я давно это писал, но я считаю, что, поскольку минимизация касается фактических платежей, лучшее решение, отвечающее ограничениям, приведет к тому, что количество уникальных платежей будет приближаться к 0. То есть, поскольку D платит A и B уже, D также не платит C. - person Mark Elliot; 15.11.2011
comment
на самом деле, поскольку у A нет возможности заплатить B или C, ограничение равенства зафиксирует целевую функцию, минимизировать нечего. - person Ben Voigt; 15.11.2011
comment
@Ben, ограничение равенства обеспечивает только то, что A получает оплату, минимизация гарантирует, что D платит как можно меньше от A до C. В этой ситуации А не может заплатить Б. - person Mark Elliot; 15.11.2011
comment
Ограничение равенства гарантирует, что целевая функция тождественно равна A_paid + B_paid + C_paid, т. е. константе, которую нельзя минимизировать путем корректировки переменных решения. - person Ben Voigt; 15.11.2011