C# 将整数分割为给定部分权重的部分算法

Question

我有一个整数和一个非负权重列表，如何将整数“拆分”为相同数量的具有相应权重的“桶”？

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)。然而，输入不一定是“好的”数字，没有好的解决方案的另一个例子是count = 150和 权重{753, 42, 95, 501}。
桶的总和必须始终等于输入count，算法应将输入尽可能接近权重地分布在桶之间。什么“尽可能接近”并不重要（例如，它可以是最低的绝对误差、相对误差或平方误差）。
我能找到的最接近的问题是“均匀地分成桶”，但是我的桶不是“均匀的”，并且“随机分成桶”，但权重是随机选择的“好”数字。

Answer 1

我建议在跟踪diff精确double值 ( v) 和舍入整数 1 ( 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