7

我有一个雇主应付的总金额，这个金额需要在员工之间分配。

例如

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

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

问题是我必须调用第 3 方系统来一一分配这些金额。但我不能让余额在分配期间低于 0 美元或高于总金额（400 美元）。

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

如果我对列表进行排序，那么负面项目排在最后。IE

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

a 会起作用，b 会起作用，但是当它尝试插入 e 时会出现资金不足错误，因为我们已经超过了 $400 的最大值。我已经意识到没有灵丹妙药，总会有一些场景会破裂。但是，我想提出一个在大多数情况下都可以使用的解决方案。

正常的数据样本将包含 5 - 100 个项目。只有 2-15% 的人含有负数。

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

4

5 回答 5

2

尽管这实际上与海尔的答案相同（我在他发布他的答案之前就开始研究答案，并击败了我）我想我还是会发布它，因为它包含一些源代码并且可能会帮助想要具体实现的人（抱歉，它不在 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;
}
于 2012-08-02T15:36:07.140 回答
1

我认为你想要在这里做的是：

  1. 过滤掉任何总是失败的值
  2. 按最小绝对值对交易进行排序 - 较小的交易意味着我们可以在达到限制之前做更多的事情
  3. 继续处理阳性，直到下一个会导致我们超过限制
  4. 继续处理底片，直到我们用完底片，或者下一个底片会让我们低于 0 美元
  5. 重复 3-4

我没有测试过下面的代码，但它应该是正确的形状：

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;
}
于 2012-08-02T13:21:08.007 回答
1

如果您想尽量减少“违反”规则的次数（低于 0$ 或超过 max$），我认为以下方法可以解决问题：

  • 在负数和正数之间拆分值

循环：

  • 选择正值的子集，使总和最大化但仍小于max，添加这些资源
  • 选择负值的子集，使其绝对值的总和最大化但仍小于您当前的余额，减去这些资源

显然，在某些时候，您会发现您正在搜索的子集不存在，因此您必须打破规则才能继续。

请注意，当您选择子集时，按顺序排序和选择较小值的贪婪方法将不起作用。

编辑：如果您可以拆分过渡，那就更容易了。继续循环。当您找不到下一个子集时，将最大值分成几部分并继续搜索。

于 2012-08-02T13:22:18.820 回答
1

您可以尝试的算法。

实现很脏，分配了许多列表，结果顺序相反。当然，在大名单上它真的很慢。

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

如果您可以拆分交易，则在您被阻止时采用托尼算法并拆分交易。

于 2012-08-02T14:30:35.373 回答
1

我认为这是一个相当困难但有趣的问题！

搜索每个排列是不可行的，因为有 n! 排序列表的方式。

一种方法可能是尝试找到不会超过总限制的正值的最佳拟合。这个问题类似于背包问题。然后，您可以再次使用相同的技术来寻找不会使您低于零的负片的最佳拟合。重复直到添加所有值。

于 2012-08-02T14:35:09.470 回答