CODEWITHSUNDEEP
algorithm
randomguy
randomguy

Reputation: 12242

Balancing algorithm to even out differences?

Say, we have N number of accounts with positive balances B_1, ..., B_n.

We can make a transfer T(from,to,amount) which moves certain amount of balance between accounts.

We have knowledge about an optimal distribution of balances O_1, ..., O_n.

The question is: How can we find the minimum set of transfers that achieve the optimal distribution? Can we always get away with N-1 transfers at most?

Example:

Balances  {0}: 10, {1}: 40, {2}: 50
Optimal   {0}: 20, {1}: 60, {2}: 20

T(2,0,10) => {0}: 20, {1}: 40, {2}: 40
T(2,1,20) => {0}: 20, {1}: 60, {2}: 20

Upvotes: 8

Views: 783

Answers (1)

NPE
NPE

Reputation: 500367

Yes, you can always get away with no more than N-1 transfer. Here is a proof by induction:

  1. For N=2, it is obvious that no more than a single transfer is required.
  2. For N>2, there are two cases:
    1. We are already at the optimal distribution, in which case there's nothing to do.
    2. There exist i and j such that B_i > O_i and B_j < O_j. Transfer min(B_i - O_i, O_j - B_j) from account i to account j. This balances one of the two accounts, thereby reducing the problem to the N-1 case.

The proof is constructive, giving you an algorithm. The algorithm does not attempt to minimise the number of transfers.

It is easy to come up with heuristics for reducing the number of steps. It is a bit late in the day for me to be thinking hard about optimality, but it would not surprise me if the problem turned out to be NP-hard.

Upvotes: 6

Related Questions