在一组值之间按比例分配(按比例分配)一个值

简单的算法草图在这里。。。

2. 对于第一项,请执行您的标准“基础除以总基础,然后乘以比例金额”。
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

TL;博士 算法具有最佳(+20%)的可能精度,速度慢70%。

接受答案中给出的评估算法 here answer 这是一个性质相似的问题。

• Amber's algorithm
• 分发2-基于 John Machin's algorithm
• 分发3-见下文
• 分发4-优化版本的 分发3

测试结果(10000次迭代)

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

在分配数量上。

1. 按正常方式分配权重
2. 增加权重 直到实际分配金额等于预期金额

通过一次以上的循环来牺牲速度和准确性。

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);
}

分发4

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);
    }
}

您的问题是定义什么是“可接受的”舍入策略,或者换句话说,您试图最小化的是什么。首先考虑这种情况:你的列表中只有2个相同的项目,并试图分配3个单位。理想情况下,您希望为每个项目分配相同的金额(1.5),但这显然不会发生。你所能做的“最好”就是分配1和2,或者2和1

• 相同的项目可能不会收到相同的分配

然后,我选择1和2而不是0和3,因为我假设您想要的是最小化完美分配和整数分配之间的差异。这可能不是你认为的“一个好的分配”,这是一个你需要思考的问题:什么会比另一个更好的分配?

在我听来,有些东西是从 Branch and Bound 可以,但这不是小事。

祝你好运!

好啊我非常确定,原始算法(如编写的)和发布的代码(如编写的)并不完全符合@Mathias所概述的测试用例的要求。

(@amt / @SumAmt) 如原问题所示。我有一个固定的$amount,需要根据为每个项目定义的百分比分割,在多个项目之间进行分割或分摊。但是,拆分%和为100%,直接乘法通常会产生小数(当被迫四舍五入为整$)加起来不等于我拆分的总数。这是问题的核心。

拿100美元,按33.333%的百分比分成3份。

使用@jtw发布的代码(假设这是原始算法的准确实现),您会得到错误的答案,即为每个项目分配33美元(总金额为99美元),因此测试失败。

• 有一个从0开始的运行总数
• 对于组中的每个项目:
• ( [Amount to be Split] * [% to Split] )
• 将累积余数计算为 [Remainder] + ( [UnRounded Amount] - [Rounded Amount] )
• Round( [Remainder], 0 ) > 1 或 当前项是列表中的最后一项,然后设置该项的分配= [Rounded Amount] + Round( [Remainder], 0 )
• [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

据我所知(我在代码中有几个测试用例),它非常优雅地处理了所有这些情况。

apportionment 问题,对此有许多已知的方法。所有这些都有某些病态:阿拉巴马悖论、人口悖论或配额规则的失败(Balinski和Young证明了没有任何方法可以避免这三种情况。)你可能想要一种遵循报价规则并避免阿拉巴马悖论的方法;人口悖论并不那么令人担忧,因为不同年份之间每月的天数没有太大差异。

http://www.sangakoo.com/en/unit/proportional-distributions-direct-and-inverse