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

Question

У меня есть последовательность чисел, например: 170, 205, 225, 190, 260, 130, 225, 160, и я должен разделить их на наборы с фиксированным числом элементов, чтобы максимальная разница *1003* между элементами наборов была минимизированной.

У меня есть гарантия, что если мне нужно разделить элементы на наборы K элементов, то общее число элементов будет равно Z * K.

Для примера с K = 4 оптимальное разбиение может быть выполнено следующим образом:

(1) : 130 160 170 190 (максимальная разница равна 60)

(2) : 205 225 225 260 (максимальная разница равна 55)

Итак, глобальная максимальная разница для этого случая равна 60.

---

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

Answer 1

Предполагая, что ваше количество чисел всегда можно разделить точно на K (то есть, не на 13 чисел в наборах по 4), это правильно.

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

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

Sorted:
[lowest, low, low, x] distance1 = x-lowest
[y, high, high, highest] distance2 = highest-y

Swapped:
[lowest, low, low, y] distance3 = y-lowest
[x, high, high, highest] distance4 = highest-x

Так как x distance1 и distance4> distance2, означаявсе стало хуже.

Это работает точно так же, если вы поместите туда более высокое значение.

Независимо от того, как далеко от номера, размещение другого числа в этом месте сделает их еще более выгодными.

Другой вариант - переместить все подмножество на один пробел влево:

[lowest, low, low, y]
[high, high, highest, x]

Но на самом деле это тот же результат, что и подкачка.

Так вот, как это работает с 2 наборами.

С тремя наборами:

[lowest, low, low, x]
[lowM, lowM, highM, highM]
[highM, y, high, highest]

Замена x и y такая же, как и ранее.Даже если x очень похож или даже равен нижнему левому максимуму (если средние минимумы и максимумы фактически равны), y все равно выше, чем x, что делает разницу с наименьшим большим, а x еще дальше от самого высокого.

Перемещение группы чисел вперед:

[lowest, low, lowM, lowM]
[highM, highM, highM, y]
[x, highM, high, highest];

Возможно, самая большая разница была между highM и наивысшим, и это расстояние теперь удалено.Но поскольку вы можете отодвинуть его от самого высокого значения, поместив туда еще более низкое значение, вы всегда ухудшаете его.Наибольшее расстояние наивысшее-высокоеM теперь является наивысшим-x, а x

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

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

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

Answer 2

Если исходная последовательность отсортирована, то соседние числа должны иметь наименьшую разницу.

Более того, элементы в начале и конце последовательности должны иметь наибольшую разницу.

В результате любой «вырез» последовательности, которая включает в себя последний элемент и первый элемент, не может быть частью решения, поскольку он включает в себя разницу, которая не минимальна.

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

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

Answer 3

Естественно, вы получите наименьшую разницу между парами чисел, отсортировав их. Вы можете получить наборы с наименьшими различиями, просто разделив отсортированные числа.

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

Если, например, у вас есть наборы 1,3,4,5 и 6,7,8,10, то вы можете переключать 5 и 6 без увеличения максимальной разницы в любой группе.

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