ИС
Переслано от Alexander Maltsev
Вопрос не по питону, а скорее по алгоритмам. Есть два множества - кредиторы и должники. Сумма долгов равна сумме всех выданных кредитов. Должнику наплевать кому возвращать долг, кредитору безразлично, от кого именно он получит назад свои деньги. Как минимизировать число транзакций?
Это NP-hard через сведение subset sum. Если кредиторов всего два, а должников n, то за n транзакций можно тогда и только тогда, когда множество должников имеет подмножество с данной суммой.