Моя проблема в том, что у меня есть заданный массив из n чисел от 1 до 100. Цель состоит в том, чтобы выбрать 5 чисел, которые дают минимальное общее расстояние. Общее расстояние рассчитывается путем суммирования расстояния каждого числа в исходном массиве до ближайшего из 5 выбранных чисел.
О чем я (вроде) пробовал и думал:
Пример
Как видите, я заблудился и просто не могу придумать решение. Вероятно, есть очень простое решение, которого я просто не понимаю.
Я просто ищу подсказку, а не решение, я не хочу разбираться в этом сам.
Всегда ли входы равномерно распределяются друг от друга, как в вашем примере?
Это кластеризация k-медиан в одном измерении. Я не думаю, что классический алгоритм максимизации ожидания точен во всех случаях, но можно написать динамическую программу.
что вы имеете в виду, когда говорите the distance of each number in the initial array
?
@CertainPerformance Нет, они случайны и могут содержать дубликаты
@TheScientificMethod Допустим, у вас есть ввод, как в примере. Для чисел 5, 10 и 15 ближайшее выбранное число - 10. Следовательно, расстояние равно 5, 0 и 5.
Вот алгоритм, который работает за полиномиальное время.
Во-первых, отсортируйте свой набор вещей n
. Затем вычислите двумерный массив, который для каждого 0 <= i <= j < n
содержит индекс оптимального элемента для заполнения диапазона от i
-го элемента до j
-го элемента. Заполните аналогичный массив общего расстояния для каждого интервала от этого оптимального массива.
В качестве примера с приведенным выше образцом выходных данных первый двумерный массив может выглядеть так:
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 элементами? Это в точности то же самое, что и диапазоны из двух элементов, Кроме, которые мы теперь разделяем между первой парой и второй парой. Но логика та же.
И наконец, как насчет нашей проблемы с 5 элементами? Это просто вопрос расчета оптимального деления между ближайшим к первым 4 элементам и самым близким к последнему. Так что просто попробуйте все возможности.
Естественным обобщением этого для заполнения k
вещей в массиве размера n
является O(n^3 log(k))
.
Не могли бы вы привести пример для первого шага относительно того, как должен выглядеть этот массив?
@Nicolas Я добавил структуры данных. Из-за симметрии входных данных матрицы очень структурированы. Со случайными числами их было бы не так много.
На каком языке это должно быть?