Minimizing the facts of payments / transportation?

Question

Search Engine Optimization

Good time of the day!
Straight to the point.
Task: Some group of people in the amount of N people, where each at different times borrowed some amount of money from someone from the same group. It is necessary to find out what is the minimum number of payment facts that can be dispensed with in order to distribute all debts. The input is debt transactions. For example:
Input:
7
DA 2
AD 10
AE 7
AF 6
BF 1
BG 5
CG 2
Output:
5
AE 7
AF 7
AG 7
BD 2
CD 6
At the moment I am doing the following.
1) I introduce the concept of balance. Initially, everyone has a zero balance. When reading the next transaction, the balance of the one who owes decreases, the balance of the one to whom they owe increases (both by the amount owed).
2) After reading all transactions, all people can be divided into two groups: with positive and negative balances. With a zero balance, you can simply discard. With a negative balance - those who owe (suppliers), with a positive balance - those who owe (consumers). The sum of all values ​​is always equal to zero (because the amount of money given is equal to the amount received). After separation, I make all values ​​positive.
3) A transport network is being built: a source is added and connected by edges to each supplier, the maximum throughput of each edge is equal to the return value, the same is done with consumers: edges are built from them to the added sink. The maximum throughput of each such edge: the receive value. Between each pair of supplier and consumer, an edge with infinite throughput (or with a total amount of giving / receiving) is built.
4) the Ford-Fulkerson algorithm is launched - we get some basis. In general, it is not yet optimal.
At this point, I'm stuck. I don’t know what to do next (all the options that I tried don’t work, if necessary, I can describe what I did).
Question: how to minimize the number of payments? Thank you!
PS I did not begin to write the mathematical formalization of the problem in the form of a system of linear equations and a function to be minimized. If necessary, please let us know in the comments.

Answer 1

Good afternoon!
Sorry for not replying for a long time. Came down with an illness on New Year's Eve. Then something did not reach the hands. Now we have arrived.
First, thank you very much!
Secondly, ported to C#. I'll write a few comments here to fix the errors that (possibly) exist in the code.
equalizer.cpp
Line 268:
for (int i = 0; i < sorted_balance.length() - 1; i++)
Why "- 1"?
Line 87:
Line 239:
if (temp.isEmpty() || temp_list.length() + 1 < temp.length())
Why "+ 1"?
Line 119:
This is:
if (!used.contains(first_key))
{
for (int j = i + 1; j < balance.keys().length(); j++)
Do this:
for (int j = i + 1; j < balance.keys().length() && !used.contains(first_key); j++)
Since first_key can end up in the used array inside the j loop
Third, about the code: so far, all of my tests pass. I'll do more tests. And now I will smoke the logic of work. Thanks again =)
In order to solve the problem, it is enough to find all the minimal subgroups in which the sum of balances is 0 (such groups do not contain other subgroups whose sum of balances is 0). Then just distribute the balances within the received subgroups "on the forehead".
To solve the first subtask, you can use: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...

Answer 2

You have made it difficult for yourself.
In this problem, money transfer chains don't make sense - they don't reduce the number of transactions. Let's say A and B have a negative balance, while C has a positive balance. A can transfer money to B, so that he transfers to C all one transaction, or everyone can transfer them directly to C, nothing will change from this.
Therefore, we can assume that there is no network, we have senders of money (those who have a negative balance) and recipients (those who have a positive one). Each sender must send money to one or more recipients.
I would suggest a simple algorithm, although I cannot prove its optimality:
1. We are looking for whether we have pairs of recipient / sender with the same balance modulo. If there is, great, we make a payment and reset their balances (forget about them).
2. Find the one who owes the most (sender)
3. Find the one who owes the largest amount (recipient)
4. Make a payment for the amount of the smallest of these two (if we have a sender who owes a total of 20, and the largest recipient should receive 11 - we make a payment from the sender to the recipient at 11)
5. Repeat until there is not a single debt left

Answer 3

Greetings!
I tried to solve your problem, and here is the result in the form of Qt code .
I propose to solve it this way:
1. With full confidence, we find a balance for transactions.
2. We delete all matches from the balance (by writing the transaction in response) and all objects with a zero balance.
3. Find the smallest modulo balance.
4. And now the sweetheart recursion begins: for each of the balances of the other sign, we create and conduct a transaction. And we run the same function with new balance values.
5. If the result obtained in paragraph 4 is the shortest in terms of the number of transactions, we happily save it and pass it up.
Naturally I am afraid of that that the recursion will be very gluttonous.