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输入，算法应该将输入分配到尽可能接近权重的桶中。什么是“尽可能接近”并不重要(例如，它可以是最低绝对误差、相对误差或平方误差)。
我能找到的最接近的问题是 Split evenly into buckets ，但是我的桶不是“偶数”和 Split randomly into buckets然而，权重是随机选择的“不错”的数字。

Answer 1

我建议四舍五入，同时跟踪精确 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