Для заданного набора чисел разделите числа на два подмножества так, чтобы разница между суммой чисел в двух подмножествах была минимальной.
Это идея, которая у меня есть, но я не уверен, что это правильное решение:
- Сортировать массив
- Возьмите первые 2 элемента. Считайте их 2 наборами (в каждом по 1 элементу)
- Возьмите следующий элемент из массива.
- Решите, в какой набор должен входить этот элемент (вычисляя сумму => она должна быть минимальной)
- Повторить
Это правильное решение? Можем ли мы сделать лучше?
задан nbro 3 March 2018 в 13:57
поделиться