Теоретически это можно сформулировать как проблему оптимизации:
По сути, мы собираемся установить набор ограничений, которые перечисляют структуру вашей проблемы, отбрасывают начальные значения и удостоверяют, что мы распределяем все деньги, как вы указали.
Начальные условия:
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, так что это не является неожиданностью.