Равномерное распределение чисел в массиве

Question

Моя проблема в том, что у меня есть заданный массив из n чисел от 1 до 100. Цель состоит в том, чтобы выбрать 5 чисел, что приведет к минимальному общему расстоянию. Общее расстояние рассчитывается путем суммирования расстояния каждого числа в исходном массиве до ближайшего из 5 выбранных чисел.

Что я (вроде) пытался и думал:

• Взять среднее число массива и разделить его на 5, чтобы получить что-то полезное?
• Разделив длину массива на 5, эти числа x, а затем первое число - массив [x], второе - массив [x * 2] и т. Д.

Пример

• Вход [5, 10, 15, 20, ..., 85, 90, 95, 100]
• Выход [10, 30, 50, 70, 90] (Возможно, будет лучший результат, но я надеюсь, что это прояснит цель)

Как видите, я довольно растерян и просто не могу найти решение. Вероятно, есть очень простое решение, которое я просто не понимаю.

Я просто ищу подсказку, а не решение, я сам не пойму этого.

Answer 1

Вот алгоритм, который работает за полиномиальное время.

Сначала рассортируйте массив из n вещей.Затем вычислите 2-мерный массив, который для каждого 0 <= i <= j < n содержит индекс оптимального элемента для заполнения диапазона от i-го элемента до j-го элемента.Заполните аналогичный массив общего расстояния для каждого интервала из этого оптимального массива.

В качестве примера с вышеприведенным примером вывода, первый 2-мерный массив может выглядеть так:

optimal_index = [
    [ 0,  0,  1,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9],
    [ 1,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10],
    [ 2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10, 10],
    [ 3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10, 10, 11],
    [ 4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10, 10, 11, 11],
    [ 5,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10, 10, 11, 11, 12],
    [ 6,  6,  7,  7,  8,  8,  9,  9, 10, 10, 11, 11, 12, 12],
    [ 7,  7,  8,  8,  9,  9, 10, 10, 11, 11, 12, 12, 13],
    [ 8,  8,  9,  9, 10, 10, 11, 11, 12, 12, 13, 13],
    [ 9,  9, 10, 10, 11, 11, 12, 12, 13, 13, 14],
    [10, 10, 11, 11, 12, 12, 13, 13, 14, 14],
    [11, 11, 12, 12, 13, 13, 14, 14, 15],
    [12, 12, 13, 13, 14, 14, 15, 15],
    [13, 13, 14, 14, 15, 15, 16],
    [14, 14, 15, 15, 16, 16],
    [15, 15, 16, 16, 17],
    [16, 16, 17, 17],
    [17, 17, 18],
    [18, 18],
    [19],
]

где индекс оптимального элемента для диапазона от i до j равен optimal_index[i][j-i].При той же схеме индексации матрица затрат будет выглядеть следующим образом:

optimal_cost = [
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280, 320, 360, 405, 450, 500],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280, 320, 360, 405, 450],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280, 320, 360, 405],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280, 320, 360],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280, 320],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100],
    [ 0, 5, 10, 20, 30, 45, 60, 80],
    [ 0, 5, 10, 20, 30, 45, 60],
    [ 0, 5, 10, 20, 30, 45],
    [ 0, 5, 10, 20, 30],
    [ 0, 5, 10, 20],
    [ 0, 5, 10],
    [ 0, 5],
    [ 0],
]

А что если мы заполним диапазоны двумя элементами?Это вопрос выбора каждого диапазона и оценки затрат в каждой точке, которые мы могли бы разделить.Эта новая структура данных просто должна содержать места для разделения между «ближайшим к первому элементу» и «ближайшим ко второму».Из этого деления мы можем взять любой диапазон и быстро разделить его на оптимальные 2, а затем сказать вам, что такое два выбранных элемента, и общую стоимость.Это может быть заполнено аналогичной матрицей.Обратите внимание, что предыдущая матрица optimal_cost сделает эти вычисления очень простыми.

Далее, как насчет диапазонов с 4 элементами?Это точно так же, как диапазоны из 2 элементов, за исключением , которые мы теперь делим между первой парой и второй парой.Но логика та же.

И, наконец, как насчет нашей проблемы с 5 элементами?Это всего лишь вопрос расчета оптимального деления между ближайшими к первым 4 элементам и ближайшими к последнему.Так что просто попробуйте все возможности.

Естественным обобщением этого для заполнения k вещей в массиве размером n является O(n^3 log(k)).