Базовое доказательство алгоритма

У меня есть последовательность чисел, например: 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.


Теперь вопрос: я предполагаю, что я могу просто отсортировать исходные данные и разбить их на равные части, начиная с начала? Если это верно, как я могу доказать это? А если нет, то какой подход мне следует использовать для решения этой проблемы?

6
задан Yippie-Ki-Yay 1 November 2011 в 07:01
поделиться