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

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

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

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

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

Я предполагаю использовать этот алгоритм в несколько более конкретном приложении. Вместо того, чтобы рассчитывать% с помощью (@ amt / @SumAmt) , как показано в исходном вопросе. У меня есть фиксированная сумма в долларах, которую нужно разделить или распределить по нескольким элементам на основе процентного разделения, определенного для каждого из этих элементов. Разделенный% суммируется до 100%, однако прямое умножение часто приводит к десятичным дробям, которые (при принудительном округлении до целых долларов) не складываются в общую сумму, которую я разделяю на части. В этом суть проблемы.

Я почти уверен, что исходный ответ от @Dav не работает в тех случаях, когда (как описано в @Mathias) округленные значения равны для нескольких фрагментов. Эту проблему с исходным алгоритмом и кодом можно подытожить одним тестовым примером:

Возьмите 100 долларов и разделите их на 3 части, используя 33,333333% в качестве вашего процента.

Использование кода, отправленного @jtw (при условии, что это точная реализация исходного алгоритма), дает неверный ответ о выделении 33 долларов на каждый элемент (в результате общая сумма составляет 99 долларов), поэтому тест не проходит.

Я думаю, что более точным алгоритмом может быть:

• Иметь промежуточную сумму, начинающуюся с 0
• Для каждого элемента в группе:
• Рассчитайте сумму распределения без округления как ([Сумма для разделения] * [% для разделения])
• Рассчитайте кумулятивный остаток как [Остаток] + ([Неокругленное количество] - [Округленное количество])
• Если Округлить ([Остаток], 0)> 1 ИЛИ текущий элемент является ПОСЛЕДНИМ ЭЛЕМЕНТОМ в списке, затем установите распределение элемента = [Округленная сумма] + Раунд ([Остаток], 0)
• иначе установите значение элемента allocation = [Округленная сумма]
• Повторите для следующего элемента

Реализовано в 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

Почти как я могу судить (а у меня есть несколько тестовых примеров в коде), все эти ситуации обрабатываются довольно изящно.