C#在给定部分权重的情况下拆分整数的算法

Question

我有一个整数和一个非负权重列表，如何将整数"拆分"为相同数量的具有相应权重的"bucket">

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

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

Answer 2

注意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 3

您可以在每次迭代中贪婪地使用天花板除法进行取整，同时检查它是否溢出count。如果它确实溢出，那么该桶中的部分就是剩余部分。

此解决方案不需要任何双点或浮点算术

public int[] SplitIntoBuckets(int count, int[] weights) {
int sum = weights.Sum(d => d);
int acc = 0;
int[] result = new int[weights.Length];
for(int i = 0; i < weights.Length; i++) {
int part_round_up = (count * weight[i] + sum - 1) / sum;

if(part_round_up + acc <= count) {
result[i] = part_round_up;
} else {
result[i] = count - acc;
}
acc += result[i];
}
return result;
}