按特定顺序分配资金

Question

我有一笔雇主支付的总金额,这笔金额需要在员工之间分配.

例如

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

应付总金额是所有项目的总和,在这种情况下是400美元

问题是我必须要求第三方系统逐一分配这些金额.但在分配期间,我不能让余额低于$ 0或高于总金额($ 400).

因此,如果我按上述顺序插入a,b,c将起作用,因此当前分配的总和= 100 + 200 - 200 = $ 100.但是,当我尝试分配d.系统将尝试添加 - $ 200,这将使当前分配的金额 - $ 100,<$ 0,这是不允许的,因此它将被系统拒绝.

如果我对列表进行排序,那么负面项目是最后的.即

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

a将工作,b将工作,但当它试图插入e时,将有不足的资金错误,因为我们已超过400美元的最大值.我已经认识到没有灵丹妙药,并且总会出现会破坏的情景.但是我想提出一个大部分时间都可以工作的解决方案.

正常的数据样本将包含5到100个项目.只有2-15%的含量为负数.

有没有一种聪明的方法可以对列表进行排序？或者只是多次尝试分配会更好.例如,将正面和负面分成两个列表.插入正数直到一个错误,然后插入负数直到它出错,然后在列表之间来回切换,直到全部分配或直到它们都出错.

Answer 1

虽然这实际上与 Haile 的答案相同（在他发布他的答案之前我就开始研究答案，并击败了我）我想我无论如何都会发布它，因为它包含一些源代码并且可能会帮助那些想要具体实现的人（抱歉，它不是用 C# 编写的，C++ 是我目前可以访问的最接近的东西）

#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;
}