7

雇用主が支払うべき総額があり、この金額をスタッフ間で分割する必要があります。

例えば

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

支払うべき合計金額は、すべてのアイテムの合計で、この場合は $400 です。

問題は、サードパーティのシステムを呼び出して、これらの金額を 1 つずつ割り当てなければならないことです。しかし、配分中に残高が 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% です。

リストを並べ替える賢い方法はありますか? または、割り当てられたものを複数回試すだけの方がよいでしょうか。たとえば、ポジティブとネガティブを 2 つのリストに分割します。1 つのエラーが発生するまでポジティブを挿入し、次にエラーが発生するまでネガティブを挿入し、リストがすべて割り当てられるまで、または両方がエラーになるまでリストを切り替えます。

4

5 に答える 5

2

これは実質的に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;
}
于 2012-08-02T15:36:07.140 に答える
1

これはかなり難しいが面白い問題だと思います！

n! 個の順列があるため、すべての順列を検索することは現実的ではありません。リストの並べ方。

1 つのアプローチは、合計制限を超えない正の値の最適な適合を見つけようとすることです。この問題はナップザック問題に似ています。次に、同じ手法を使用して、ゼロを下回らない最適なネガを探すことができます。すべての値が追加されるまで繰り返します。

于 2012-08-02T14:35:09.470 に答える
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;
}

トランザクションを分割できる場合は、Tony のアルゴリズムを使用して、ブロックされたときにトランザクションを分割します。

于 2012-08-02T14:30:35.373 に答える