Найдите подмножество с элементами, которые наиболее удалены друг от друга

Это можно решить за полиномиальное время с помощью DP.

Первый шаг, как вы упомянули, - это сортировка списка A. Пусть X[i,j] будет решением для выбора элементов j из первых элементов i A.

Теперь X[i+1, j+1] = max( min( X[k,j], A[i+1]-A[k] )) над k‹=i.

Я оставлю шаг инициализации и запоминание шага подмножества для вас.

В вашем примере (1,2,6,10) это работает следующим образом:

    1    2   6   10
1   -    -   -    -
2   -    1   5    9
3   -    -   1    4
4   -    -   -    1

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

Я не могу придумать полиномиальный алгоритм для решения этой проблемы, поэтому я бы предложил один из двух вариантов.

Один из них заключается в использовании алгоритма поиска в стиле ветвей и границ, поскольку у вас под рукой есть хорошая эвристика: верхняя граница для любого решения — это минимальный размер промежутка между выбранными элементами, поэтому первое предположение (равномерно разнесенные ячейки, как вы предложили), может дать вам хорошую основу, которая поможет сразу обрезать большинство ветвей. Это будет нормально работать для меньших значений k, хотя наихудшая производительность — O(N^k).

Другой вариант — начать с той же базовой линии, рассчитать для нее минимальное попарное расстояние, а затем попытаться улучшить ее. Допустим, у вас есть подмножество с минимальным расстоянием 10, теперь попробуйте получить подмножество с 11. Это легко сделать с помощью жадного алгоритма — выберите первый элемент в отсортированной последовательности так, чтобы расстояние между ним и предыдущим элементом было больше. -или-равно расстоянию, которое вы хотите. Если получилось, попробуйте увеличить еще, если не получилось -- такого подмножества нет.

Последнее решение может быть быстрее, когда массив большой и k тоже относительно большой, но элементы в массиве относительно малы. Если они связаны некоторым значением M, этот алгоритм займет O(N*M) времени, или, с небольшим улучшением, O(N*log(M)), где N — размер массива.

Как предполагает в своем ответе Евгений Клюев, существует также хорошая верхняя граница максимального попарного расстояния, которую можно использовать в любом из этих алгоритмов. Так что сложность последнего на самом деле O(N*log(M/k)).

Я полагаю, ваш набор заказан. Если нет, мой ответ будет немного изменен.

Let's suppose you have an array X = (X1, X2, ..., Xn)

Energy(Xi) = min(|X(i-1) - Xi|, |X(i+1) - Xi|), 1 < i <n

j <- 1
while j < n - k do
    X.Exclude(min(Energy(Xi)), 1 < i < n)
    j <- j + 1
    n <- n - 1
end while

$length = length($array);
sort($array); //sorts the list in ascending order
$differences = ($array << 1) - $array; //gets the difference between each value and the next largest value
sort($differences);  //sorts the list in ascending order
$max = ($array[$length-1]-$array[0])/$M; //this is the theoretical max of how large the result can be
$result = array();
for ($i = 0; i < $length-1; $i++){
    $count += $differences[i];
    if ($length-$i == $M - 1 || $count >= $max){ //if there are either no more coins that can be taken or we have gone above or equal to the theoretical max, add a point
        $result.push_back($count);
        $count = 0;
        $M--;
    }
}
return min($result)

Для некодовых людей: отсортируйте список, найдите различия между каждыми двумя последовательными элементами, отсортируйте этот список (в порядке возрастания), затем выполните цикл по нему, суммируя последовательные значения, пока вы либо не пройдете теоретический максимум, либо не останется достаточного количества элементов. ; затем добавьте это значение в новый массив и продолжайте, пока не достигнете конца массива. затем верните минимум вновь созданного массива.

Хотя это всего лишь набросок. На первый взгляд, любая операция здесь может быть выполнена за линейное время (сортировка по системе счисления для сортировок).

Например, с 1, 4, 7, 100 и 200 и M=3 мы получаем:

$differences = 3, 3, 93, 100
$max = (200-1)/3 ~ 67
then we loop:
$count = 3, 3+3=6, 6+93=99 > 67 so we push 99
$count = 100 > 67 so we push 100
min(99,100) = 99

Это простое упражнение, чтобы преобразовать это в заданное решение, которое я оставляю читателю (P.S. после того, как я все время читал это в книге, я всегда хотел это сказать: P)