I need an algorithm to optimally transfer values based on amounts needed to other accounts. For example given the accounts below what is an algorithm/psuedocode to transfer values from accounts that have excess to deficient accounts, also without causing deficiency in positive accounts?
Account1 Balance: 0 Needed:.17853 Account2 Balance: 0 Needed:.1789524 Account3 Balance: 0.296 Needed:.4278 Account4 Balance: 0 Needed:.50231 Account5 Balance: 0.1 Needed:.17853 Account6 Balance: 0 Needed:.89 Account7 Balance: 4.0 Needed:0 Account8 Balance: 1.2447183721375 Needed:.894762
For the moment I'm gonna assume that you don't need to know where the money is coming from. (We can handle that later) You can use two for loops:
First loop) Go through all elements and collect the excess values. In your example, this will result 4 excess from account 7 and ~0.3 excess from account 8, which is a total of 4.3.
Second loop) Look at each account with deficiency, give it what it needs from what you current excess value and then update the excess value. In your example, when you see account 1 needs .17, you give it that much and then update your available excess from 4.3 to 4.3-0.17 = 4.13. And you continue until the last element.
If you want to know who contributed to resolve the deficiency then instead of keeping a sum and updating it, you should collect a list of accounts that have excess value in step 1 and update that list in step 2.
Again in your case, the list would be something like (Account 7, 4.0)->(Account 8, 0.3) and in step to use Account 7 as long as you can and when it runs out, you move on to Account 8.
Time complexity is O(n) and optimal.