例如

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％的含量为负数.

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

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