我有一笔雇主支付的总金额,这笔金额需要在员工之间分配.
例如
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％的含量为负数.
有没有一种聪明的方法可以对列表进行排序？或者只是多次尝试分配会更好.例如,将正面和负面分成两个列表.插入正数直到一个错误,然后插入负数直到它出错,然后在列表之间来回切换,直到全部分配或直到它们都出错.
解决方法
虽然这实际上和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;
}
