алгоритм для определения минимальных платежей среди группы

Мое мнение: Вы все усложняете.

Думайте об этом как о «пуле» денег и полностью теряйте отношения:

Вместо:

• Майк должен Джону 100
• Джон должен Рэйчел 200
• Майк должен Рэйчел 400

Алгоритм должен только подумать:

• Майк должен 100
• Джон должен 100
• Джон должен 200
• Рэйчел должен 200
• Майк должен 400
• Рэйчел должен 400

Вычисление:

• Майк должен 500
• Джон должен 100
• Рэйчел должен 600

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

Later Edit

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

Взгляните на эту статью в блоге « Оптимальная балансировка счета », которая точно описывает вашу проблему .

если каждый из A, B и C должен по 1 доллару каждому из D, E и F, решение «список» или «центральный банк» создает пять транзакций (например, A, B, C - 3 доллара -> D, D - $ 3-> E, F), тогда как наивное решение приводит к девяти транзакциям. Однако, если A должен только D, B только E и C только F, решение центрального банка по-прежнему создает пять транзакций (A, B, C - 1 доллар-> D, D - 1 доллар-> E, F), тогда как лучший для решения нужно всего три (A - $ 1-> D, B - $ 1-> E, C - $ 1-> F). Это показывает, что решение «список» или «центральный банк» не является оптимальным в целом.

Следующий жадный алгоритм может использоваться для создания лучших решений проблемы, но они не всегда оптимальны. Пусть «долг [i, j]» обозначает сумму денег, которую лицо i должно лицу j; изначально этот массив инициализируется в соответствии с ситуацией.

repeat until last:
  find any (i, j) such that |K = {k : debt[i,k] > 0 and debt[j,k] > 0}| >= 2
  if such (i, j) found:
     // transfer the loans from i to j
     total = 0
     for all k in K:
       debt[j,k] += debt[i,k]
       total += debt[i,k]
       debt[i,k] = 0 
     person i pays 'total' to person j
  else:
     last

for every i, j in N:
  if (debt[i,j] > 0)
    person i pays debt[i,j] to person j

Ключевым моментом этого алгоритма является наблюдение, что если и A, и B должны деньги как C, так и D, вместо четырех транзакций, необходимых для прямых платежей, B может заплатить долг перед A, который может позаботиться о выплате ссуд как A, так и B.

Чтобы увидеть, как работает этот алгоритм, рассмотрим случай, когда A, B и C владеют 1 долларом каждому из D, E, F:

1. A переводит долги A на B и платит 3 доллара B (одна транзакция)
2. B переводит долги B C и платит 6 долларов C (одна транзакция)
3. Только C имеет долги; C платит по 3 доллара D, E и F каждому (три транзакции)

. Но в случае, когда A должен D, B должен E, а C должен F, алгоритм немедленно переходит в цикл платежей, приводя к оптимальному количеству транзакций (только три) вместо пяти, которые были бы результатом подхода «центрального банка».

Примером неоптимальности является то, что A должен D и E, B должен E и F. и C должен F и D (предположим, что 1 доллар на каждый долг). Алгоритм не может объединить ссуды, потому что у двух плательщиков нет двух общих получателей. Это можно исправить, заменив "> = 2" во второй строке на "> = 1", но тогда алгоритм, скорее всего, станет очень чувствительным к порядку обеспечения долгов.

Алгоритм не может объединить ссуды, потому что у двух плательщиков нет двух общих получателей. Это можно исправить, изменив «> = 2» во второй строке на «> = 1», но тогда алгоритм, скорее всего, станет очень чувствительным к порядку обеспечения долгов.

Алгоритм не может объединить ссуды, потому что у двух плательщиков нет двух общих получателей. Это можно исправить, заменив "> = 2" во второй строке на "> = 1", но тогда алгоритм, скорее всего, станет очень чувствительным к порядку обеспечения долгов.

Хотя я согласен с @Andrew в том, что преобразование этого в проблему с графом, вероятно, слишком сложно, я не уверен, что его подход дает минимальное количество транзакций. Так вы решите проблему в реальной жизни, чтобы избавиться от головной боли; просто объедините деньги.

Несколько шагов, которые кажутся «правильными»:

• Удалите всех лиц с нулевым долгом; им не нужно отправлять или получать деньги от кого-либо.
• Соедините всех дающих и получателей с одинаковыми суммами задолженности / задолженности. Поскольку минимальная возможность подключения на узел ненулевого долга равна 1, их транзакции уже минимальны, если они просто платят друг другу. Удалите их с графика.
• Начиная с лица, имеющего наибольшую сумму для выплаты, создайте список всех получателей с задолженностью меньше этой суммы. Попробуйте все комбинации платежей, пока не найдете ту, которая удовлетворит большинство получателей одной транзакцией. «Сохраните» оставшийся излишек долга.
• Переходите к следующему по величине дателю и т. Д.
• Распределите весь излишек долга среди оставшихся получателей.

Как всегда, боюсь, я почти уверен в этом. первые два шага, менее уверены в остальных. В любом случае это действительно похоже на проблему из учебника; Я уверен, что есть «правильный» ответ.