Как разделить набор на два подмножества так, чтобы разница между суммой чисел в двух наборах была минимальной?

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

Это идея, которая у меня есть, но я не уверен, что это правильное решение:

  1. Сортировать массив
  2. Возьмите первые 2 элемента. Считайте их 2 наборами (в каждом по 1 элементу)
  3. Возьмите следующий элемент из массива.
  4. Решите, в какой набор должен входить этот элемент (вычисляя сумму => она должна быть минимальной)
  5. Повторить

Это правильное решение? Можем ли мы сделать лучше?

48
задан nbro 3 March 2018 в 13:57
поделиться