Пропорционально распределить (пропорционально) значение по набору значений

Ответ 1

Простой алгоритм эскиза здесь...

• Иметь общее число, начинающееся с нуля.
• Сделайте свой стандартный "разделите основу на общую базу, затем умножьте на количество долей" для первого элемента.
• Сохраните исходное значение текущей работы в другом месте, затем добавьте сумму, которую вы только что рассчитали, в # 2.
• Завершите как старое значение, так и новое значение текущей суммы целых чисел (не изменяйте существующие значения, не округлите их до отдельных переменных) и не используйте разницу.
• Число, вычисленное на шаге 4, - это значение, присвоенное текущему основанию.
• Повторите шаги № 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

Ответ 2

TL; DR с лучшей (+ 20%) возможной точностью, на 70% медленнее.

Проявленные алгоритмы, представленные в принятом ответе здесь, а также ответ на вопрос python аналогичного характера.

• Распространение 1 - на основе Янтарный алгоритм
• Распространение 2 - на основе алгоритма Джона Мачина
• Распространение 3 - см. ниже
• Распределить 4 - оптимизированную версию Распространять 3 (например, удалить LINQ, используемые массивы)

Результаты тестирования (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 имеет точность на 19,9%, что на 70,7% меньше, чем ожидалось.

Распределить 3

Делает все возможное, чтобы максимально быть максимально точным при распределении суммы.

• Распределите веса как обычно
• Приращение веса с максимальной ошибкой до фактической распределенной суммы равно ожидаемой сумме.

Достигает скорости для точности, делая более одного прохода через петлю.

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

Ответ 3

Ok. Я вполне уверен, что исходный алгоритм (как написано) и отправленный код (как написано) не совсем отвечают на почту для тестового примера, описанного @Mathias.

Мое намеренное использование этого алгоритма - несколько более конкретное приложение. Вместо вычисления% используя (@amt / @SumAmt), как показано в исходном вопросе. У меня есть фиксированная сумма, которая должна быть разделена или распределена по нескольким элементам на основе% split, определенного для каждого из этих элементов. Разделение% сумм до 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 allocation = [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

Насколько я могу судить (и у меня есть несколько тестовых примеров в коде), это довольно эффективно обрабатывает все эти ситуации.

Ответ 4

Проблема заключается в том, чтобы определить, что такое "приемлемая" политика округления, или, другими словами, то, что вы пытаетесь свести к минимуму. Рассмотрим сначала эту ситуацию: у вас есть только 2 одинаковых элемента в вашем списке и пытаются выделить 3 единицы. В идеале вы хотели бы выделить одну и ту же сумму для каждого элемента (1.5), но это явно не произойдет. "Лучшее", что вы могли бы сделать, скорее всего, выделит 1 и 2, или 2 и 1. Итак,

• может быть несколько решений для каждого размещения
• идентичные элементы могут не получать одинаковое распределение

Затем я выбрал 1 и 2 над 0 и 3, потому что я предполагаю, что вы хотите минимизировать разницу между идеальным распределением и целым распределением. Возможно, это не то, что вы считаете "хорошим распределением", и это вопрос, о котором вам нужно подумать: что бы сделать распределение лучше, чем другое?
Одной возможной функцией значения может быть минимизация "общей ошибки", т.е. Сумма абсолютных значений различий между вашим распределением и "идеальным", неограниченным распределением.
Мне кажется, что что-то, вдохновленное Branch and Bound, может работать, но это нетривиально. Предполагая, что решение Dav всегда создает распределение, которое удовлетворяет ограничению (что, я надеюсь, это так), я полагаю, что не гарантировано дать вам "лучшее" решение, "лучшее", определяемое любым показателем расстояния/соответствия, в конечном итоге принятие. Моя причина в том, что это жадный алгоритм, который в задачах целочисленного программирования может привести вас к решениям, которые действительно не подходят для оптимального решения. Но если вы можете жить с "несколько правильным" распределением, то я говорю, иди за ней! Выполнение этого "оптимально" не кажется тривиальным.
Удачи!

Ответ 5

Это проблема apportionment, для которой существует много известных методов. У всех есть определенные патологии: парадокс Алабамы, парадокс населения или отказ от правила квоты. (Балински и Янг доказали, что ни один метод не может избежать всех трех.) Вероятно, вы захотите, чтобы он следовал правилу цитаты и избегал парадокса Алабамы; парадокс населения не так сильно беспокоит, так как нет большого различия в количестве дней в месяц между разными годами.

Ответ 6

Я думаю, что пропорциональные распределения - это ответ: http://www.sangakoo.com/en/unit/proportional-distributions-direct-and-inverse