Как к круглым плаваниям к целым числам при сохранении их суммы?

Один из вариантов, который вы можете попробовать, - это «каскадное округление».

Для этого алгоритма вы отслеживаете два промежуточных результата: одно из чисел с плавающей запятой и одно целое число до сих пор. , Чтобы получить следующее целое число, вы добавляете следующее число fp к вашей промежуточной сумме, округляя промежуточную сумму, а затем вычитаете целую промежуточную сумму из округленной промежуточной суммы: -

number  running total   integer integer running total
   1.3       1.3          1           1
   1.7       3.0          2           3
   1.9       4.9          2           5
   2.2       8.1          3           8
   2.8      10.9          3          11
   3.1      14.0          3          14

Один из действительно простых способов - взять все дробные части и суммировать их. Это число по определению вашей проблемы должно быть целым числом. Распределите это целое число равномерно, начиная с наибольшего из ваших чисел. Затем присваивайте одно второму по величине числу ... и т. Д., Пока не закончится что-то распространять.

Примечание. Это псевдокод ... и может быть отключен на единицу в индексе ... его поздно и Я сонный.

float accumulator = 0;

for (i = 0; i < num_elements; i++)  /* assumes 0 based array */
{
   accumulator += (fn[i] - floor(fn[i])); 
   fn[i] =  (fn[i] - floor(fn[i]);
}

i = num_elements;

while ((accumulator > 0) && (i>=0))
{
    fn[i-1] += 1;   /* assumes 0 based array */
    accumulator -= 1;
    i--;
}

Обновление: Существуют и другие методы распределения накопленных значений на основе того, сколько усечения было выполнено для каждого значения. Это потребует сохранения отдельного списка под названием loss [i] = fn [i] - floor (fn [i]). Затем вы можете повторить список fn [i] и повторно присвоить 1 элементу наибольших потерь (затем установите для потерь [i] значение 0). Это сложно, но я думаю, что это работает.

Как насчет:

a) start: array is [0.1, 0.2, 0.4, 0.5, 0.8], N=3, presuming it's sorted
b) round them all the usual way: array is [0 0 0 1 1]
c) get the sum of the new array and subtract it from N to get the remainder.
d) while remainder>0, iterate through elements, going from the last one
   - check if the new value would break rule 3.
   - if not, add 1
e) in case that remainder<0, iterate from first one to the last one
   - check if the new value would break rule 3.
   - if not, subtract 1

Можете ли вы попробовать что-то вроде этого?

in [i] = fn [i] - int (fn [i]);
fn_res [i] = fn [i] - in [i];

fn_res → является результирующей дробью. (Я думал, что это было основным ...), Мы что-то упустили?

Ну, 4 это болевая точка. В противном случае вы можете сделать такие вещи, как «обычно округлять и накапливать остаток; округлять при накоплении> = 1». (редактировать: на самом деле, это все еще может быть в порядке, пока вы поменялись местами?)

Может быть, есть способ сделать это с помощью линейного программирования? (это математика «программирование», а не компьютерное программирование - вам понадобится немного математики, чтобы найти выполнимое решение, хотя вы, вероятно, можете пропустить обычную часть «оптимизации»).

В качестве примера линейного программирования - с примером [1.3, 1.7, 1.9, 2.2, 2.8, 3.1] вы можете иметь правила:

1 <= i < 2
1 <= j < 2
1 <= k < 2
2 <= l < 3
3 <= m < 4
i <= j <= k <= l <= m
i + j + k + l + m = 13

Затем примените некоторую линейную / матричную алгебру ;-p Подсказка: есть продукты для выполнения вышеупомянутого, основанные на таких вещах, как алгоритм «Симплекс». Обычный университетский корм (я написал один в универе для своего финального проекта).

Проблема, на мой взгляд, заключается в том, что алгоритм сортировки не указан. Или больше похоже - стабильная сортировка или нет.

Рассмотрим следующий массив с плавающей точкой:

[0,2 0,2 ​​0,2 ​​0,2 ​​0,2]

Сумма равна 1. Тогда целочисленный массив должен быть:

[0 0 0 0 1]

Однако, если алгоритм сортировки не стабилен, он может отсортировать «1» где-нибудь еще в массиве ...

Сделайте так, чтобы суммированные различия были меньше 1, и проверьте, чтобы они были отсортированы. что-то вроде

while(i < sizeof(fn) / sizeof(float)) {
    res += fn[i] - floor(fn[i]);
    if (res >= 1) {
        res--;
        in[i] = ceil(fn[i]);
    }
    else
        in[i] = floor(fn[i]);
    if (in[i-1] > in[i])
        swap(in[i-1], in[i++]);
}

(это бумажный код, поэтому я не проверял действительность.)

Essentially what you'd do is distribute the leftovers after rounding to the most likely candidates.

1. Round the floats as you normally would, but keep track of the delta from rounding and associated index into fn and in.
2. Sort the second array by delta.
3. While sum(in) < N, work forwards from the largest negative delta, incrementing the rounded value (making sure you still satisfy rule #3).
4. Or, while sum(in) > N, work backwards from the largest positive delta, decrementing the rounded value (making sure you still satisfy rule #3).

Example:

[0.02, 0.03, 0.05, 0.06, 0.07, 0.08, 0.09, 0.1, 0.11, 0.12, 0.13, 0.14] N=1

1. [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] sum=0
and [[-0.02, 0], [-0.03, 1], [-0.05, 2], [-0.06, 3], [-0.07, 4], [-0.08, 5], 
     [-0.09, 6], [-0.1, 7], [-0.11, 8], [-0.12, 9], [-0.13, 10], [-0.14, 11]]

2. sorting will reverse the array

3. working from the largest negative remainder, you get [-0.14, 11].
Increment `in[11]` and you get [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] sum=1 
Done.