Как мне округлить набор чисел, при этом общее количество добавляет к 1

Question

Я ищу способ округлить набор чисел до ближайшего рационального числа, сохраняя при этом общее значение набора.

Я хочу распределить общее значение '1' среди переменныхколичество полей без учета иррациональных чисел.

Итак, я хочу распределить сумму по трем полям.Я не хочу, чтобы каждое значение было 0,33333333333333333333 '.Я бы предпочел 0,33, 0,33 и 0,34.

Я хотел бы реализовать это с помощью Jquery / javascript.У меня есть форма, где поля добавляются динамически.По умолчанию общая сумма равномерно распределяется по каждому полю, однако моя проблема еще более усложняется, потому что часто значение не будет одинаково распределено между всеми полями.Некоторые значения могут быть более взвешенными.Поэтому, если бы мне пришлось изменить одно из трех значений на 0,5, два других значения были бы скорректированы до 0,25.

Может кто-нибудь помочь с подходящим алгоритмом?

Answer 1

Не идеально, но легко написать:

1. Округлить каждое число до ближайшего приемлемого значения.По ходу следите за тем, какое число вы округлили в большую сторону до наибольшей суммы, а какое число вы округлили в большую сторону до наибольшей суммы.
2. Суммируйте числа в большую сторону.
3. Вычтите эту сумму из 1
4. Если разница отрицательная, добавьте ее к числу, которое вы округлили в большую сторону.Если разница положительная, добавьте ее к числу, которое вы округлили в большую сторону.

Answer 2

Идеальная (и более простая) версия подхода Джона Родригеса:

Округлите все числа вниз, сохраните остатки для дальнейшего использования.

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

Answer 3

У меня проблемы с пониманием вашего описания проблемы, но я надеюсь, что оно эквивалентно следующему:

INPUT : список действительных чисел x_1, x_2, ..., x_n суммируется в целое число N

OUTPUT : список целых чисел y_1, y_2, ..., y_n также суммируется до N, так что y_i либо x_i округляется в меньшую сторону, либо округляется в большую сторону(т. е. y_i отличается от x_i менее чем на 1).

Вот один из способов сделать это:

• Вычислить последовательность частичных сумм s_0 = 0, s_1= x_1, s_2 = x_1 + x_2, ..., s_n = x_1 + ... + x_n = N.

• Округление каждой частичной суммы до ближайшего целого числа (округление до полных целых чиселв последовательном направлении, скажем, вверх), образуя последовательность t_0 = 0, t_1 = s_1, округленную до ближайшего целого числа, ..., t_n = N.

• Пусть y_1 = t_1- t_0, ..., y_n = t_n - t_ {n-1}.

Тогда y_i являются целыми числами, которые суммируются с N и для каждого i, s_i - 0,5

Answer 4

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

Это легко сделать с рациональнымчисла:

a/b + c/d + ... = x/z
a*z/x/b + c*z/x/d + ... = 1

Но, из вашего примера, я не думаю, что это то, что вы просите ... Если вы хотите, чтобы каждое число имело не более 2 десятичных знаков, это то же самое, что и штрафцелочисленное решение задачи * 100, которое совпадает с поиском целых чисел j, k, l для решения этой оптимизации:

minimize (j-a*100)^2 + (k-b*100)^2 + (l-c*100)^2
 s.t.  (j + k + l) = 100    

вы можете восстановить действительные значения для a, b, c как:

a = j/100.;
b = k/100.;
c = l/100.;

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

Answer 5

Как я понимаю, у нас есть куча неотрицательных значений с плавающей точкой между 0 и 1, которые составляют 1, и мы хотим округлить каждое до двух десятичных разрядов, не меняя тот факт, что они составляют 1.

Во-первых, масштабируйте числа в 100 раз, чтобы у нас были x_1, ..., x_n, которые в сумме равны 100. Теперь нам нужно округлить их до целых чисел, чтобы они по-прежнему суммировались до 100.

Давайтезапишите frac (x) для дробной части x, которая может быть вычислена как x - int (x).Обратите внимание, что 0 <= frac (x) <1. </p>

Сначала рассмотрим сумму дробных частей frac (x_1) + frac (x_2) + ... + frac (x_n).Это значение является целым числом от 0 до n-1.Давайте назовем F. Простой способ вычислить F так: 100 - (int (x_1) + ... + int (x_n)).(Это также может быть самый простой способ увидеть, что сумма дробных частей представляет собой целое число!)

Небольшая мысль должна убедить вас, что это целое число F - количество раз, которое вам нужно округлить, иследовательно, nF - это количество раз, которое вам нужно округлить.Следовательно, отсортируйте ваш исходный список от наименьшего к наибольшему по дробной части, затем округлите число первых nF и округлите число последних F.

Например, если у нас есть числа 1/7, 1/6, 8/42, 1/10, 1/11, 34/110 (да, сумма равна 1), мы умножаем на 100 изапишите в десятичном виде: 14,2857, 16,66666, 19,047619, 10, 9,090909, 30,90909.Целые части: 14, 16, 19, 10, 9, 30, что в сумме равно 98. Это означает, что F = 2, nF = 4.Сортировка чисел по дробным частям дает: 10, 19,047619, 9,090909, 14,2857, 16,66666, 30,90909.Так как F = 2 и nF = 4, округляем последние два и округляем первые четыре.В этом примере этот метод эквивалентен округлению до ближайшего, но, конечно, он не всегда будет работать таким образом!

Answer 6

Я бы сказал, что самый простой способ сделать это - начать с 100. Затем (я собираюсь предположить, что у вас есть целые веса на точках), скажем, у вас есть веса 1 1 2 3 4, сложите полученные веса11 (n), распределите 11 или (100 / n) для каждого веса, который вы получите:

9 9 18 27 36

Затем сложите новые веса, чтобы получить 99, выполните100-99 = 1, затем распределите оставшуюся сумму на минимальную гранулярность, которую вы хотите, и распределите ее по ячейкам со случайным распределением проб на основе весов.Возможно, вы захотите сдвинуться, а затем сделать этот шаг, несмотря на некоторую неточность.Вы можете использовать 1000 или выше, если вы хотите больше детализации.Я также думаю, что это должно работать, если у вас есть нецелочисленные веса, у вас просто останется больше на последнем шаге для распределения.

Answer 7

Вы говорите о дробях. Для трех чисел 1 / n, 1 / m, 1 / o найдите наименьший общий знаменатель x из n, m, o и сделайте 1 / x своей единицей. Тогда каждый из трех будет автоматически иметь значения n / x, m / x и o / x (целые единицы 1 / x), и его не нужно будет округлять до конечного результата, где бы это ни было.