按比例分配（按比例分配）一组值的值

我需要根据列表中“基础”值的相对权重编写将在列表中按比例分配值的代码。 简单地将“基础”值除以“基础”值的总和，然后将该因子乘以原始值以按比例分配工作：

proratedValue = (basis / basisTotal) * prorationAmount; 

但是，必须将此计算的结果舍入为整数值。 舍入的效果意味着列表中所有项目的proratedValue总和可能与原始prorationAmount不同。

任何人都可以解释如何应用“无损”比例算法，该算法在列表中尽可能准确地按比例分配值，而不会出现舍入错误？

Answer 1

这里简单的算法草图……

1. 运行总计从零开始。
2. 对于第一项，您的标准“按总分基础划分，然后乘以比例”。
3. 将运行总计的原始值存储在其他位置，然后在＃2中添加刚刚计算的数量。
4. 将运行总计的旧值和新值四舍五入为整数（不要修改现有值，将它们四舍五入为单独的变量），并采取差异。
5. 在步骤4中计算的数字是分配给当前基础的值。
6. 每个基础重复步骤＃2-5。

这保证按比例分配的总金额等于输入的比例分配金额，因为您实际上从未实际修改过运行总计（您只需将其舍入值用于其他计算，您不会将其写回）。 现在处理整数舍入的问题，因为舍入误差将在运行总计中随时间累加，并最终在另一个方向上跨越舍入阈值。

基本示例：

 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 

Answer 2

TL; DR算法具有最佳（+ 20％）可能的准确度，减慢70％。

Evaulated算法在这里被接受的答案中呈现以及回答类似性质的python问题。

• 分配1 – 基于Amber的算法
• 分配2 – 基于John Machin的算法
• 分发3 – 见下文
• 分发4 – Distribute 3的优化版本（例如，删除了LINQ，使用过的数组）

测试结果（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) 

方法3的准确度提高了19.9％，执行时间比预期慢70.7％。

分发3

尽最大努力尽可能准确地分配金额。

1. 正常分配权重
2. 增加具有最高误差的权重，直到实际分配量等于预期量

牺牲通过循环多次传递来提高准确性。

 public static IEnumerable Distribute3(IEnumerable 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); } 

分发4

 public static IEnumerable Distribute4(IEnumerable 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 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); } } 

Answer 3

好。 我很确定原始算法（如编写的）和发布的代码（如编写的）并不完全回答@Mathias概述的测试用例的邮件。

我对此算法的预期用途是稍微更具体的应用程序。 而不是计算原始问题中显示的％using (@amt / @SumAmt) 。 我有固定的$金额，需要根据为每个项目定义的％拆分进行拆分或分散。 拆分％总和为100％，但是，直接乘法通常会产生小数（当被强制舍入到整数$时）不会累加到我分开的总量。 这是问题的核心。

我很确定@Dav的原始答案在（如@Mathias描述的）多个切片的舍入值相等的情况下不起作用。 原始算法和代码的这个问题可以用一个测试用例总结：

花费100美元并将其分为3种方式，使用33.333333％作为百分比。

使用@jtw发布的代码（假设这是原始算法的准确实现），会给你错误的答案，即为每个项目分配33美元（导致总计99美元），因此它未通过测试。

我认为更准确的算法可能是：

• 运行总计从0开始
• 对于组中的每个项目：
• 将未舍入的分配金额计算为( [Amount to be Split] * [% to Split] )
• 将累积余数计算为[Remainder] + ( [UnRounded Amount] - [Rounded Amount] )
• 如果Round( [Remainder], 0 ) > 1 或者当前项目是列表中的最后项目，则设置项目的分配= [Rounded Amount] + Round( [Remainder], 0 )
• else set item的分配= [Rounded Amount]
• 重复下一个项目

在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 

尽可能接近（我在代码中有几个测试用例），这可以非常优雅地处理所有这些情况。

Answer 4

您遇到的问题是定义“可接受的”舍入策略是什么，或者换句话说，您要尝试最小化的是什么。 首先考虑这种情况：列表中只有2个相同的项目，并且正在尝试分配3个单元。 理想情况下，您希望为每个项目分配相同的金额（1.5），但这显然不会发生。 你能做的“最好的”可能是分配1和2，或2和1

• 每个分配可能有多个解决方案
• 相同的项目可能无法获得相同的分配

然后，我选择1和2超过0和3，因为我假设你想要的是最小化完美分配和整数分配之间的差异。 这可能不是你认为“一个好的分配”，这是一个你需要考虑的问题：什么会使分配比另一个好？
一个可能的值函数可以是最小化“总误差”，即您的分配与“完美”，无约束分配之间的差异的绝对值之和。
听起来， 分支和绑定所启发的东西可以起作用，但这并非易事。
假设Dav解决方案总是产生满足约束条件的分配（我信任的情况就是这种情况），我认为不能保证给你“最佳”解决方案，“最好”由任何距离/拟合度量定义你最终采用。 我的理由是这是一个贪婪的算法，在整数编程中，问题会导致你找到真正偏离最佳解决方案的解决方案。 但是如果你能接受“有点正确”的分配，那么我说，去吧！ “最佳地”做到这一点听起来并不重要。
祝你好运！

Answer 5

这是一个分配问题，有许多已知的方法。 所有人都有某些病态：阿拉巴马州悖论，人口悖论或配额规则失败。 （Balinski和Youngcertificate没有任何方法可以避免这三种方法。）你可能想要一个遵循引用规则并避免阿拉巴马悖论的方法; 由于不同年份之间每月的天数没有太大差异，因此人口悖论并不是一个问题。

Answer 6

我认为比例分布是答案： http ： //www.sangakoo.com/en/unit/proportional-distributions-direct-and-inverse