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

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

О чем я (вроде) пробовал и думал:

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

Пример

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

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

Я просто ищу подсказку, а не решение, я не хочу разбираться в этом сам.

На каком языке это должно быть?

GBlodgett 10.09.2018 01:10

Всегда ли входы равномерно распределяются друг от друга, как в вашем примере?

CertainPerformance 10.09.2018 01:12

Это кластеризация k-медиан в одном измерении. Я не думаю, что классический алгоритм максимизации ожидания точен во всех случаях, но можно написать динамическую программу.

David Eisenstat 10.09.2018 01:42

что вы имеете в виду, когда говорите the distance of each number in the initial array?

The Scientific Method 10.09.2018 01:55

@CertainPerformance Нет, они случайны и могут содержать дубликаты

DevNico 10.09.2018 12:03

@TheScientificMethod Допустим, у вас есть ввод, как в примере. Для чисел 5, 10 и 15 ближайшее выбранное число - 10. Следовательно, расстояние равно 5, 0 и 5.

DevNico 10.09.2018 12:05
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
6
400
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

Во-первых, отсортируйте свой набор вещей 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)).

Не могли бы вы привести пример для первого шага относительно того, как должен выглядеть этот массив?

DevNico 10.09.2018 12:06

@Nicolas Я добавил структуры данных. Из-за симметрии входных данных матрицы очень структурированы. Со случайными числами их было бы не так много.

btilly 10.09.2018 19:58

Другие вопросы по теме