Allocate money in a specific order

Question

I have the total amount paid by the Employer, this amount should be divided between the staff.

for example

a $100 b $200 c -$200 d -$200 e $500 

The total amount payable is the sum of all items, in this case $ 400

The problem is that I have to call a third-party system to assign these amounts one at a time. But I cannot allow the balance to remain below $ 0 or above the total amount ($ 400) during the distribution.

So, if I insert into the above order, then a, b, c will work so that the current allocated amount = 100 + 200 - 200 = 100 dollars. However, when I try to highlight d. The system will try to add - $ 200, which will make the current allocated amount - $ 100, $ 0, which is not allowed, so the system will be rejected.

If I sort the list, the negative elements will be the last. i.e.

 a $100 b $200 e $500 c -$200 d -$200 

a will work, b will work, but when he tries to insert e, there will be a lack of funds, because we have exceeded a maximum of $ 400. I came to understand that there is no silver bullet, and there will always be scenarios of what will break. However, I wanted to find a solution that would work most of the time.

A normal data sample will contain from 5 to 100 units. Only 2-15% of them contain negative amounts.

Is there a trick to sorting the list? Or it would be better to just try highlighted several times. For example, divide the positive and negative into two lists. Insert positive values ​​until one error, then insert negatives until errors appear, then switch back and forth between the list until it is highlighted, or until both errors are.

Answer 1

Although this is actually the same as Haile, the answer (I started working on the answer before he posted it and beat me before the hit), I thought that I would publish it anyway, as it includes some source code and can help someone who wants a specific implementation (sorry this is not in C #, C ++ is the closest thing I have access to at the moment)

 #include <iostream> #include <vector> #include <numeric> #include <algorithm> using namespace std; vector<int> orderTransactions(const vector<int>& input) { int max = accumulate(input.begin(), input.end(), 0); vector<int> results; // if the sum is negative or zero there are no transactions that can be added if (max <= 0) { return results; } // split the input into positives and negatives vector<int> sorted = vector<int>(input); sort(sorted.begin(), sorted.end()); vector<int> positives; vector<int> negatives; for (int i = 0; i < sorted.size(); i++) { if (sorted[i] >= 0) { positives.push_back(sorted[i]); } else { negatives.push_back(sorted[i]); } } // try to process all the transactions int sum = 0; while (!positives.empty() || !negatives.empty()) { // find the largest positive transaction that can be added without exceeding the max bool positiveFound = false; for (int i = (int)positives.size()-1; i >= 0; i--) { int n = positives[i]; if ((sum + n) <= max) { sum += n; results.push_back(n); positives.erase(positives.begin()+i); positiveFound = true; break; } } if (positiveFound == true) { continue; } // if there is no positive find the smallest negative transaction that keep the sum above 0 bool negativeFound = false; for (int i = (int)negatives.size()-1; i >= 0; i--) { int n = negatives[i]; if ((sum + n) >= 0) { sum += n; results.push_back(n); negatives.erase(negatives.begin()+i); negativeFound = true; break; } } // if there is neither then this as far as we can go without splitting the transactions if (!negativeFound) { return results; } } return results; } int main(int argc, const char * argv[]) { vector<int> quantities; quantities.push_back(-304); quantities.push_back(-154); quantities.push_back(-491); quantities.push_back(-132); quantities.push_back(276); quantities.push_back(-393); quantities.push_back(136); quantities.push_back(172); quantities.push_back(589); quantities.push_back(-131); quantities.push_back(-331); quantities.push_back(-142); quantities.push_back(321); quantities.push_back(705); quantities.push_back(210); quantities.push_back(731); quantities.push_back(92); quantities.push_back(-90); vector<int> results = orderTransactions(quantities); if (results.size() != quantities.size()) { cout << "ERROR: Couldn't find a complete ordering for the transactions. This is as far as we got:" << endl; } for (int i = 0; i < results.size(); i++) { cout << results[i] << endl; } return 0; } 

Answer 2

I think you want to do this:

• Filter out any values ​​that will always fail
• Order transactions at the smallest absolute value - smaller transactions mean that we can do more before we reach the limit
• Continue to process positive values ​​until the next one leads us to exceed the limit
• Continue to process negatives until we run out of denial, or the following leads us to $ 0
• Repeat 3-4

I have not tested the code below, but it should be vaguely correct in form:

 var validValues = values .Where(v => Math.Abs(v) < upperLimit) //filter out anything that will always fail .OrderBy(v => Math.Abs(v)); //sort by the absolute value (to maximise # of transactions) var additions = validValues.Where(v => v >= 0); var subtractionsEnumerator = validValues.Where(v => v < 0).GetEnumerator(); var currentTotal = 0.0; //go through all of the additions foreach (var addition in additions) { if (currentTotal + addition > upperLimit) //would the next addition take us over the limit? { //keep processing negative values until the next one would take us past $0 while (subtractionsEnumerator.MoveNext() && currentTotal + subtractionsEnumerator.Current > 0) { currentTotal += subtractionsEnumerator.Current; } } if (currentTotal + addition > upperLimit) //if we weren't able to reduce by enough throw new Exception("Can't process transactions"); currentTotal += addition; } //do we have any left over negatives? better process those as well while (subtractionsEnumerator.MoveNext()) { if (currentTotal + subtractionsEnumerator.Current < 0) throw new Exception("Can't process transactions"); currentTotal += subtractionsEnumerator.Current; } 

Answer 3

If you want to minimize the number of times you “break” the rules (go under $ 0 or more max $), I think the following will do the trick:

• Separate values ​​between negative and positive

Loop

• Choose a subset of positive values so that the maximum amount , but still less than max , add these resources
• Select a subset of negative values so that the sum of their absolute values ​​is maximized , but still less than the current balance , subtracts these resources

It is clear that at some point you will find that the subset you are looking for does not exist, so you will have to break the rule to continue.

Note that the greedy approach of sorting and selecting smaller values ​​in order will not work when you select the subsets.

EDIT: If you can split the transition, it's even easier. Just continue the cycle. When you cannot find the next subset, divide the largest value into parts and continue the search.

Answer 4

An algorithm that you can try.

The implementation is dirty, many lists are highlighted, and the result is in reverse order. Of course, he is very slow on large lists.

 static List<int> GetDeepestPossibility(List<int> values, int sum = 0) { List<int> deepest = new List<int>(); for (int i = 0; i < values.Count; i++) { if (Allowed(values[i] + sum)) { List<int> subValues = new List<int>(values); subValues.RemoveAt(i); List<int> possibility = GetDeepestPossibility(subValues, values[i] + sum); possibility.Add(values[i]); if (possibility.Count + 1 > deepest.Count) { possibility.Add(values[i]); deepest = possibility; if (deepest.Count == values.Count - 1) break; } } } return deepest; } private static bool Allowed(int p) { return p >= 0 && p <= 600; } 

If you can split transactions, take the Tony algorithm and split the transaction when you are locked.

Answer 5

I think this is a rather difficult but interesting problem!

It is not possible to search for each permutation, since there exists n! ways to organize the list.

One approach may be to try to find the best fit for positive values ​​that do not exceed the overall limit. This problem is then similar to Knapsack . Then you could find the best fit for the negatives, which will not lead you to zero, again using the same technique. Repeat until all values ​​are added.