时间戳

首页 > 解决方案 > C# split integer in parts given part weights algorithm

c# - C# split integer in parts given part weights algorithm

问题描述

I have an integer and a list of non-negative weights, how can I 'split' the integer into same number of 'buckets' with corresponding weights? 

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

A trivial example would be count = 200 and weights = { 25, 25, 50 } with solution {50, 50, 100} (50+50+100 = 200). The inputs, however, does not have to be 'nice' numbers, another example without nice solution would be count = 150 and weights {753, 42, 95, 501}.
The sum of buckets must be always equal to the count input, the algorithm should distribute the input among buckets as closely to weights as possible. What is as 'close as possible' does not matter (for example it could be either lowest absolute, relative or squared error).
The closest questions I could find are Split evenly into buckets, however my buckets are not 'even' and Split randomly into buckets however the weights are chosen randomly to be 'nice' numbers.

标签： c#algorithmintegerdouble

解决方案

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

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

推荐阅读