我需要编写代码，根据列表中“基数”值的相对权重，在列表中对值进行按比例分配。简单地将“基数”值除以“基数”值的总和，然后通过因子乘以原始值来按比例分配，可以在一定程度上实现：
proratedValue = (basis / basisTotal) * prorationAmount;
然而，这种计算的结果必须舍入为整数值。舍入的效果意味着列表中所有项目的proratedValue之和可能与原始prorationAmount不同。
有人能解释一下如何应用“无损”分配算法，以尽可能准确地按比例分配价值到列表中，而不会遭受舍入误差吗？
这里有一个简单的算法草图...
这种方法能够保证总金额按比例分配，因为您从未实际修改累加器本身（您只针对其他计算采用了它的舍入值，而没有写回这些值）。以前可能会存在的整数舍入误差问题现在已得到解决，因为舍入误差将随时间积累在累加器中，并最终推动一个值超过舍入阈值进入另一个方向。
基本示例：
Input basis: [0.2, 0.3, 0.3, 0.2]
Total prorate: 47
----
R used to indicate running total here:
R = 0
First basis:
oldR = R [0]
R += (0.2 / 1.0 * 47) [= 9.4]
results[0] = int(R) - int(oldR) [= 9]
Second basis:
oldR = R [9.4]
R += (0.3 / 1.0 * 47) [+ 14.1, = 23.5 total]
results[1] = int(R) - int(oldR) [23-9, = 14]
Third basis:
oldR = R [23.5]
R += (0.3 / 1.0 * 47) [+ 14.1, = 37.6 total]
results[1] = int(R) - int(oldR) [38-23, = 15]
Fourth basis:
oldR = R [37.6]
R += (0.2 / 1.0 * 47) [+ 9.4, = 47 total]
results[1] = int(R) - int(oldR) [47-38, = 9]
9+14+15+9 = 47
TL;DR算法准确率最佳（+20%），但速度较慢（慢70%）。
本文介绍了在here所提出的评估算法，以及类似问题的Python问题的answer。
测试结果（10,000次迭代）
Algorithm | Avg Abs Diff (x lowest) | Time (x lowest)
------------------------------------------------------------------
Distribute 1 | 0.5282 (1.1992) | 00:00:00.0906921 (1.0000)
Distribute 2 | 0.4526 (1.0275) | 00:00:00.0963136 (1.0620)
Distribute 3 | 0.4405 (1.0000) | 00:00:01.1689239 (12.8889)
Distribute 4 | 0.4405 (1.0000) | 00:00:00.1548484 (1.7074)
方法三的准确率比预期提高了19.9％，但执行时间慢了70.7％。
尽最大努力在分配金额时保持尽可能准确。
通过多次循环牺牲速度以换取准确性。
public static IEnumerable<int> Distribute3(IEnumerable<double> weights, int amount)
{
var totalWeight = weights.Sum();
var query = from w in weights
let fraction = amount * (w / totalWeight)
let integral = (int)Math.Floor(fraction)
select Tuple.Create(integral, fraction);
var result = query.ToList();
var added = result.Sum(x => x.Item1);
while (added < amount)
{
var maxError = result.Max(x => x.Item2 - x.Item1);
var index = result.FindIndex(x => (x.Item2 - x.Item1) == maxError);
result[index] = Tuple.Create(result[index].Item1 + 1, result[index].Item2);
added += 1;
}
return result.Select(x => x.Item1);
}
public static IEnumerable<int> Distribute4(IEnumerable<double> weights, int amount)
{
var totalWeight = weights.Sum();
var length = weights.Count();
var actual = new double[length];
var error = new double[length];
var rounded = new int[length];
var added = 0;
var i = 0;
foreach (var w in weights)
{
actual[i] = amount * (w / totalWeight);
rounded[i] = (int)Math.Floor(actual[i]);
error[i] = actual[i] - rounded[i];
added += rounded[i];
i += 1;
}
while (added < amount)
{
var maxError = 0.0;
var maxErrorIndex = -1;
for(var e = 0; e < length; ++e)
{
if (error[e] > maxError)
{
maxError = error[e];
maxErrorIndex = e;
}
}
rounded[maxErrorIndex] += 1;
error[maxErrorIndex] -= 1;
added += 1;
}
return rounded;
}
static void Main(string[] args)
{
Random r = new Random();
Stopwatch[] time = new[] { new Stopwatch(), new Stopwatch(), new Stopwatch(), new Stopwatch() };
double[][] results = new[] { new double[Iterations], new double[Iterations], new double[Iterations], new double[Iterations] };
for (var i = 0; i < Iterations; ++i)
{
double[] weights = new double[r.Next(MinimumWeights, MaximumWeights)];
for (var w = 0; w < weights.Length; ++w)
{
weights[w] = (r.NextDouble() * (MaximumWeight - MinimumWeight)) + MinimumWeight;
}
var amount = r.Next(MinimumAmount, MaximumAmount);
var totalWeight = weights.Sum();
var expected = weights.Select(w => (w / totalWeight) * amount).ToArray();
Action<int, DistributeDelgate> runTest = (resultIndex, func) =>
{
time[resultIndex].Start();
var result = func(weights, amount).ToArray();
time[resultIndex].Stop();
var total = result.Sum();
if (total != amount)
throw new Exception("Invalid total");
var diff = expected.Zip(result, (e, a) => Math.Abs(e - a)).Sum() / amount;
results[resultIndex][i] = diff;
};
runTest(0, Distribute1);
runTest(1, Distribute2);
runTest(2, Distribute3);
runTest(3, Distribute4);
}
}
好的。我非常确定原始算法（如所写）和发布的代码（如所写）并不能完全回答@Mathias概述的测试用例问题。
我打算使用此算法进行稍微更具体的应用。而不是像原始问题中所示，使用(@amt / @SumAmt)来计算百分比。我有一定的固定金额需要根据每个项目定义的百分比分割或分配到多个项目上。分割百分比总和为100％，但直接乘法经常会导致小数点（强制四舍五入为整个$时）不等于我正在分开的总金额。这是问题的核心。
我相当确定@Dav的原始答案在（如@Mathias所描述的）四舍五入值在多个切片间相等的情况下不起作用。这个原始算法和代码的问题可以通过一个测试用例来概括：
拿$100并使用33.333333％将其分成3份。
使用@jtw发布的代码（假设这是原始算法的准确实现）会给出错误答案，将$33分配给每个项目（导致总和为$99），因此未能通过测试。
我认为一个更准确的算法可能是：
([要拆分的金额] * [％要拆分])[余数]+([未舍入的金额]-[舍入的金额])Round([余数]，0）> 1或当前项目是列表中的最后一个项目，则将该项目的分配设置为[舍入的金额]+ Round ([余数]，0)[舍入的金额]在T-SQL中实现，它看起来像这样：
-- Start of Code --
Drop Table #SplitList
Create Table #SplitList ( idno int , pctsplit decimal(5, 4), amt int , roundedAmt int )
-- Test Case #1
--Insert Into #SplitList Values (1, 0.3333, 100, 0)
--Insert Into #SplitList Values (2, 0.3333, 100, 0)
--Insert Into #SplitList Values (3, 0.3333, 100, 0)
-- Test Case #2
--Insert Into #SplitList Values (1, 0.20, 57, 0)
--Insert Into #SplitList Values (2, 0.20, 57, 0)
--Insert Into #SplitList Values (3, 0.20, 57, 0)
--Insert Into #SplitList Values (4, 0.20, 57, 0)
--Insert Into #SplitList Values (5, 0.20, 57, 0)
-- Test Case #3
--Insert Into #SplitList Values (1, 0.43, 10, 0)
--Insert Into #SplitList Values (2, 0.22, 10, 0)
--Insert Into #SplitList Values (3, 0.11, 10, 0)
--Insert Into #SplitList Values (4, 0.24, 10, 0)
-- Test Case #4
Insert Into #SplitList Values (1, 0.50, 75, 0)
Insert Into #SplitList Values (2, 0.50, 75, 0)
Declare @R Float
Declare @Results Float
Declare @unroundedAmt Float
Declare @idno Int
Declare @roundedAmt Int
Declare @amt Float
Declare @pctsplit Float
declare @rowCnt int
Select @R = 0
select @rowCnt = 0
-- Define the cursor
Declare SplitList Cursor For
Select idno, pctsplit, amt, roundedAmt From #SplitList Order By amt Desc
-- Open the cursor
Open SplitList
-- Assign the values of the first record
Fetch Next From SplitList Into @idno, @pctsplit, @amt, @roundedAmt
-- Loop through the records
While @@FETCH_STATUS = 0
Begin
-- Get derived Amounts from cursor
select @unroundedAmt = ( @amt * @pctsplit )
select @roundedAmt = Round( @unroundedAmt, 0 )
-- Remainder
Select @R = @R + @unroundedAmt - @roundedAmt
select @rowCnt = @rowCnt + 1
-- Magic Happens! (aka Secret Sauce)
if ( round(@R, 0 ) >= 1 ) or ( @@CURSOR_ROWS = @rowCnt ) Begin
select @Results = @roundedAmt + round( @R, 0 )
select @R = @R - round( @R, 0 )
End
else Begin
Select @Results = @roundedAmt
End
If Round(@Results, 0) <> 0
Begin
Update #SplitList Set roundedAmt = @Results Where idno = @idno
End
-- Assign the values of the next record
Fetch Next From SplitList Into @idno, @pctsplit, @amt, @roundedAmt
End
-- Close the cursor
Close SplitList
Deallocate SplitList
-- Now do the check
Select * From #SplitList
Select Sum(roundedAmt), max( amt ),
case when max(amt) <> sum(roundedamt) then 'ERROR' else 'OK' end as Test
From #SplitList
-- End of Code --
这将为测试用例生成最终结果集：
idno pctsplit amt roundedAmt
1 0.3333 100 33
2 0.3333 100 34
3 0.3333 100 33