Конвертировать поплавки в целые с заданной суммой

Question

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

Другими словами, идеальный результат рассчитывается по input_float / sum_of_floats * target_sum.Пример: Учитывая значения с плавающей точкой 0.1, 0.2, 0.5 и целевую сумму 16, результат должен быть 2, 4, 10.

К сожалению, цифры не так хороши в реальности, поэтому я хотел бы минимизировать ошибку по сравнению с реальным, идеальным результатом.

Например, если целью было 17,это должно быть 2, 4, 11.Первый float конвертируется в 0.1 / 0.8 * 17 = 2.125.Второе и третье соответственно 4.25 и 10.6.Ясно, что 10,6 следует округлить.

Однако простого округления на границе 0,5 не всегда достаточно.Во-первых, существует патологический случай масштабирования входных данных 1, 1 для суммирования 3: одно из значений должно быть 2, а другое 1, поэтому есть два эквивалентных решения.

Во-вторых, может потребоваться округление по-разному: Учитывая 0.1, 0.1, 0.3 и цель 8, мы получаем 0.1 / 0.5 * 8 = 1.6 => 2 и 0.3 / 0.5 * 8 = 4.8 => 5, суммируя до 2 + 2 + 5 = 9 вместо 8.

Что было бы хорошим решением для этого примера?Это приходит на ум:

• 1, 1, 6
• 1, 2, 5
• 2, 2, 4

С 1.6 - 1 и т. Д.мы видим, что первый имеет абсолютные ошибки 0.6, 0.6, 1.2.Как правило, я бы хотел сложить их в квадрат, чтобы получить:

• 1, 1, 6 -> (1.6 - 1)^2 + (1.6 - 1)^2 + (4.8 - 6)^2 = 0.36 + 0.36 + 1.44 = 2.16
• 1, 2, 5 -> (1.6 - 1)^2 + (1.6 - 2)^2 + (4.8 - 5)^2 = 0.36 + 0.16 + 0.04 = 0.56
• 2, 2, 4 -> (1.6 - 2)^2 + (1.6 - 2)^2 + (4.8 - 4)^2 = 0.16 + 0.16 + 0.64 = 0.96

Соответственно, 1, 2, 5 (или 2, 1, 5) должно быть предпочтительным.

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

Я работаю в C / C ++ / C # -подобных языках, но здесь меня интересует только общий алгоритм.

Answer 1

1. Рассчитать идеальные значения с плавающей запятой.
2. Создание значений кандидатов путем округления до целых.
3. Пока сумма кандидатов
   • Увеличение кандидата с наибольшей ошибкой на 1

В питоне:

   def convert(weights, target):
       ideals = [v/sum(weights) * target for v in weights]
       candidates = [int(math.floor(t)) for t in ideals]
       while (sum(candidates) < target):
            err = [(c-i)*(c-i) for c,i in zip(candidates, ideals)]
            candidates[err.index(max(err)]+=1
        return candidates

Answer 2

Возможно, вы будете рады узнать, что находитесь на пороге оптимального решения. Есть два основных шага:

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

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

Приводит ли это к решению?

Answer 3

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

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

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

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

Answer 4

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

Пусть нам нужна сумма S.
Масштабировать все значения, и для каждого масштабированного v составить пару Int(v), Frac(v), вычислить сумму частей int -скажем ISum, затем увеличьте int части S-ISum пар с наибольшими дробными частями