Разбиение массива с плавающей точкой

Question

В то время как писать код, я нашел следующую проблему, изложить ее простым способом:

Partition массив поплавки Х в массиве и B, такие что разность между суммой значений в и сумма значений B минимизируется

Это было частью расследования, которое я делал, но я не могу найти способ эффективно выполнять эту операцию.

Edit:

Чтобы ответить тем, кто считает, что это из конкурса по математике, как PE, SPOJ или домашнее задание, это не так. Я просто интересовался этим, когда я пытался разбить уже факторизованное число p в набор факторов a и b такой, что b = a + 1. Если мы берем журналы с обеих сторон, мы можем показать, что эта проблема эквивалентна минимизации разности сумм, но именно там я застрял.

Answer 1

Просто первая простая идея. Используйте методы динамического программирования.
Я предполагаю, что эта проблема может быть преобразована в проблему ранца. Вам нужно выбрать предметы из X (будет массив A), чтобы максимизировать сумму, но не превышать (sumX - sumA) значение (будет сумма элементов из массива B). Для алгоритма решения проблемы ранца методом динамического программирования смотрите wiki, например.
Это решение может быть неправильным, кстати ... но даже если это сработает, я более чем уверен, что существуют более эффективные, элегантные и короткие решения.