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

Это было бы оптимальным решением, но мне действительно нужно только точное решение для ограничения размера подмножества. Разница сумм не обязательно должна быть минимальной, но должна быть близкой. Также я бы предпочел, чтобы меньший набор (если есть) имел большую сумму.

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

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

arbitrarily divide the set into two sets of the same size (or 1 element size difference)
do
  diffOfSums := sum1 - sum2
  foundBetter := false
  betterDiff := 0.0

  foreach pair of elements from set1 and set2 do
    if |diffOfSums - 2 * betterDiff| > |diffOfSums - 2 * (value1 - value2)| then
      foundBetter := true
      betterDiff := value1 - value2
    endif
  done

  if foundBetter then swap the found elements
while foundBetter

Моя проблема с этим подходом заключается в том, что я не уверен в реальной сложности и в том, можно ли ее улучшить. Это, конечно, не соответствует требованию оставить меньшее подмножество с большей суммой.

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