Оптимальный способ перевода баланса счета между людьми

Question

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

Пример

+--------+---------+
| person | balance |
+--------+---------+
| A      | 7 500   |
| B      | -2 500  |
| C      | -10 000 |
| D      | 15 000  |
+--------+---------+

В этом примере каждый должен получить баланс o 2 500. Для этого:

• Человек А должен перевести 5 000 человеку Б
• Человек D должен перевести 12 500 человеку C

Подводя итог, у меня есть следующие данные:

• количество человек (> = 2)
• начальный баланс каждого человека
• какой баланс должен иметь каждый человек после перевода

Есть ли какой-нибудь алгоритм для этого? Это NP-полная проблема?

Answer 1

Эта проблема NP-сложная. По сути, это эквивалентно этой другой проблеме :

Учитывая группу людей и количество кредитов и дебетов, найдите минимальное количество переводов между этими людьми для урегулирования всех кредитов и debits.

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