C# 在给定部分权重算法的部分中拆分整数

Question

我有一个整数和一个非负权重列表，我怎样才能将整数 'split' 转换为具有相应权重的相同数量的 'buckets'？

public int[] SplitIntoBuckets(int count, int[] weights) {
    // some magic algorithm
    Debug.Assert(solution.Sum() == count);
    return solution;
}

一个简单的例子是 count = 200 和 weights = { 25, 25, 50 } 以及解决方案 {50, 50, 100} (50+50+100 = 200)。然而，输入不一定是 'nice' 数字，另一个没有好的解决方案的例子是 count = 150 和权重 {753, 42, 95, 501}.
桶的总和必须始终等于 count 输入，算法应尽可能接近权重地在桶之间分配输入。 'close as possible' 是什么并不重要（例如，它可以是最低绝对误差、相对误差或平方误差）。
我能找到的最接近的问题是 Split evenly into buckets, however my buckets are not 'even' and Split randomly into buckets 但是权重是随机选择的 'nice' 个数字。

Answer 1

注意 solution[i] 等于：

round(weights[i] / weightSum * count)

存在一种极端情况，其中 weights[i] / weightSum * count 是二分之一 (x.5) 的奇数倍，这会导致 round 不必要地舍入额外的时间。例如 count = 3、weights = { 1, 1 }。为了解决这个问题，我们通过从 count 中减去前面的桶的总和来计算最后一个桶。这将确保解决方案无论如何加起来 count。

public int[] SplitIntoBuckets(int count, int[] weights) {
    int[] solution = new int[weights.Length];
    int weightSum = weights.Sum();
    // for every weight except the last...
    int sum = 0;
    for (int i = 0 ; i < weights.Length - 1 ; i++) {
        solution[i] = (int)Math.Round((double)weights[i] / weightSum * count);
        sum += solution[i];
    }
    // calculate the last bucket by subtracting:
    solution[weights.Length - 1] = count - sum;
    return solution;
}

Answer 2

我建议在跟踪精确 double 值 (v) 和四舍五入整数一 (value) 之间的差异 (diff) 时进行舍入：

public static int[] SplitIntoBuckets(int count, int[] weights) {
  if (null == weights)
    throw new ArgumentNullException(nameof(weights));
  else if (weights.Length <= 0)
    return new ArgumentOutOfRangeException(nameof(weights), "Empty weights");  

  double sum = weights.Sum(d => (double)d);

  if (sum == 0)
    throw new ArgumentException("Weights must not sum to 0", nameof(weights));

  Func<double, int> round = (double x) => (int)(x >= 0 ? x + 0.5 : x - 0.5);

  int[] result = new int[weights.Length];
  double diff = 0;

  for (int i = 0; i < weights.Length; ++i) {
    double v = count * (double)(weights[i]) / sum;
    int value = round(v);
    diff += v - value;

    if (diff >= 0.5) {
      value += 1;
      diff -= 1;
    }
    else if (diff <= -0.5) {
      value -= 1;
      diff += 1;
    }

    result[i] = value;
  }
    
  return result;
}

演示：

string demo = sstring.Join(Environment.NewLine, Enumerable
  .Range(200, 15)
  .Select(n => $"{n} = {string.Join(", ", SplitIntoBuckets(n, new int[] { 25, 25, 50 }))}"));

Console.Write(demo);

结果：

200 = 50, 50, 100
201 = 50, 51, 100
202 = 51, 50, 101
203 = 51, 51, 101
204 = 51, 51, 102
205 = 51, 52, 102
206 = 52, 51, 103
207 = 52, 52, 103
208 = 52, 52, 104
209 = 52, 53, 104
210 = 53, 52, 105
211 = 53, 53, 105
212 = 53, 53, 106
213 = 53, 54, 106
214 = 54, 53, 107

C# 在给定部分权重算法的部分中拆分整数

C# split integer in parts given part weights algorithm

c#

algorithm

double

integer