Кто кому должен оптимизация денег

Допустим, у вас есть n человек, каждый из которых должен друг другу деньги. В общем, должно быть возможно уменьшить количество транзакций, которые необходимо совершить. т. е. если X должен Y 4 фунта стерлингов, а Y должен X 8 фунтов стерлингов, то Y должен только заплатить X 4 фунта стерлингов (1 транзакция вместо 2).

Это становится труднее, когда X должен Y, но Y должен Z, который должен X как хорошо. Я вижу, что вы можете легко рассчитать один конкретный цикл. Мне помогает, когда я думаю о нем как о полностью связном графике, причем границами является сумма, которую должен каждый человек.

Проблема кажется NP-полной, но, тем не менее, какой алгоритм оптимизации я мог бы сделать, чтобы уменьшить общее количество транзакций? Не обязательно быть настолько эффективным, так как N для меня довольно мало.

Изменить:

Цель этой проблемы - иметь в системе учета что-то, что может сказать каждому человеку, когда он войти в систему «Вы можете удалить M транзакций, просто заплатив кому-то X сумму, а кому-то Y сумму». Следовательно, банковское решение (хотя и оптимальное, если все платят одновременно) здесь не может быть использовано.