У меня есть последовательность чисел, например: 170, 205, 225, 190, 260, 130, 225, 160
и я должен разбить их на наборы с фиксированным числом элементов, чтобы максимальная разница между элементами наборов была минимальной .
У меня есть гарантия, что если мне нужно разбить элементы на наборы по K
элементов, то общее количество элементов будет равно Z * K
.
Для примера с K = 4
оптимальное разделение может быть выполнено следующим образом:
(1): 130 160 170 190
(максимальная разница равна 60)
( 2): 205 225 225 260
(максимальная разница равна 55)
Итак, глобальная максимальная разница для этого случая равна 60.
Теперь вопрос: я предполагаю, что я могу просто отсортировать исходные данные и разбить их на равные части, начиная с начала? Если это верно, как я могу доказать это? А если нет, то какой подход мне следует использовать для решения этой проблемы?