Блог

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

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

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

Например, если целевым значением было 17, оно должно быть 2, 4, 11 . Первое значение с плавающей точкой преобразуется в 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 #-подобных языках, но здесь меня интересует только общий алгоритм.

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

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

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

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

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

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

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

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

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

Это приведет вас к решению?

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

В python:

    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