Получение минимально возможной суммы из разницы чисел

Ответ 1

Решение от marcog - это правильное, нерекурсивное, многочленное решение проблемы - это довольно стандартная проблема DP - но, только для полноты, здесь доказательство того, что он работает, и фактический код для проблемы. [@marcog: Не стесняйтесь скопировать любую часть этого ответа в свой собственный, если хотите; Я удалю это.]

Proof

Пусть список будет x ₁,..., x _N. Предположим, что wlog отсортирован по списку. Мы пытаемся найти K (непересекающиеся) пары элементов из списка, так что сумма их разностей сведена к минимуму.

Претензия. Оптимальное решение всегда состоит из различий в последовательных элементах.
Доказательство. Предположим, вы исправили подмножество элементов, чьи различия взяты. Затем по доказательству предоставленному Джонасом Кёлькером, оптимальное решение только для этого подмножества состоит из различий в последовательных элементах из списка. Предположим теперь, что существует решение, соответствующее подмножеству, которое не содержит пар последовательных элементов, т.е. Решение включает в себя разность x _j -x _i, где j > я + 1, Затем мы можем заменить x _j на x _{я + 1}, чтобы получить меньшую разность, так как x _i ≤ x _{я + 1} ≤ x _j ⇒ x _{я + 1} -x _i ≤ x _j -x _i.
(Излишне говорить, что если x _{я + 1}= x _j, то взятие x _{я + 1} неотличимо от принятия x _j.) Это доказывает утверждение.

Остальное - просто рутинное произведение динамического программирования: оптимальное решение с использованием k пар из первых n элементов либо вообще не использует n-й элемент (в этом случае это просто оптимальное решение с использованием k пар из первого n- 1), или использует n-й элемент, в этом случае это разность x _n -x _n-1 плюс оптимальное решение с использованием k- 1 пара из первого n-2.

Вся программа работает во времени O (N log N + NK), как говорит marcog. (Сортировка + DP.)

Код

Здесь полная программа. Я ленился с инициализацией массивов и написал код Python с помощью dicts; это небольшой логарифмический (N) коэффициент с использованием реальных массивов.

'''
The minimum possible sum|x_i - x_j| using K pairs (2K numbers) from N numbers
'''
import sys
def ints(): return [int(s) for s in sys.stdin.readline().split()]

N, K = ints()
num = sorted(ints())

best = {} #best[(k,n)] = minimum sum using k pairs out of 0 to n
def b(k,n):
    if best.has_key((k,n)): return best[(k,n)]
    if k==0: return 0
    return float('inf')

for n in range(1,N):
    for k in range(1,K+1):
        best[(k,n)] = min([b(k,n-1),                      #Not using num[n]
                           b(k-1,n-2) + num[n]-num[n-1]]) #Using num[n]

print best[(K,N-1)]

Проверьте это:

Input
4 2
1515 1520 1500 1535
Output
30

Input
8 3
1731 1572 2041 1561 1682 1572 1609 1731
Output
48

Ответ 2

Внесение изменений в учетную запись:

Начните с сортировки списка. Затем используйте динамическое программирующее решение с состоянием i, n, представляющим минимальную сумму n разностей при рассмотрении только первых чисел я в последовательности. Начальные состояния: dp [*] [0] = 0, все остальное = бесконечность. Используйте два цикла: внешний цикл, проходящий через я от 1 до N, внутренний цикл, проходящий через n от 0 до R (3 в вашем примере в вашем редактировании - это использует 3 пары чисел, что означает 6 отдельных номеров). Ваше рекуррентное отношение: dp [i] [n] = min (dp [i-1] [n], dp [i-2] [n-1] + seq [i] - seq [i-1]).

Вы должны знать об обработке граничных случаев, которые я проигнорировал, но общая идея должна работать и работать в O (N log N + NR) и использовать O (NR) пространство.

Ответ 3

Я предполагаю, что общая проблема такова: учитывая список из 2n целых чисел, выведите список из n пар, так что сумма | x - y | по всем парам (x, y) как можно меньше.

В этом случае идея была бы следующей:

• сортировать числа
• emit (numbers[2k], numbers[2k+1]) для k = 0, ..., n - 1.

Это работает. Доказательство:

Предположим, что у вас есть x_1 < x_2 < x_3 < x_4 (возможно, с другими значениями между ними) и вывода (x_1, x_3) и (x_2, x_4). Тогда

|x_4 - x_2| + |x_3 - x_1| = |x_4 - x_3| + |x_3 - x_2| + |x_3 - x_2| + |x_2 - x_1| >= |x_4 - x_3| + |x_2 - x_1|.

Другими словами, всегда лучше выводить (x_1, x_2) и (x_3, x_4), потому что вы не дублируете пространство между x_2 и x_3 дважды. По индукции наименьшее число 2n должно быть сопряжено со вторым наименьшим числом; по индукции по остальной части списка, спаривание самых маленьких соседей всегда оптимально, поэтому предложенный алгоритм эскиза верен.

Ответ 4

Закажите список, затем выполните разностный расчет.

EDIT: hi @hey

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

Скажем, у вас есть список L из N целых чисел, вы должны сформировать пары k (с 2*k <= N)

Создайте функцию, которая найдет наименьшую разницу в списке (если список отсортирован, он будет быстрее;) назовите его smallest(list l)

Создайте еще один, который найдет то же самое для двух пар (может быть сложным, но выполнимым) и называть его smallest2(list l)

Определите best(int i, list l) функцию, которая дает лучший результат для пар i в списке L

Алгоритм выглядит следующим образом:

• best (1, L) = наименьшее (L)
• best (2, L) = smallest2 (L)
• для я от 1 до k:

петли

compute min ( 
    stored_best(i-2) - smallest2( stored_remainder(i-2) ),
    stored_best(i-1) - smallest( stored_remainder(i-1) 
) and store as best(i)
store the remainder as well for the chosen solution

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

(Работа по переключению выполняется с помощью smallest2)

Ответ 5

Шаг 1: Рассчитайте разности пар

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

Number Diff
====== ====
1561
        11
1572
         0
1572
        37
1609
        73
1682
        49
1731
         0
1731
       310
2041

Сохраните различия в массиве или таблице или какой-либо другой структуре данных, где вы можете поддерживать различия и два числа, которые способствовали каждой разнице. Назовите это DiffTable. Это должен выглядеть примерно так:

Index Diff Number1 Number2
===== ==== ======= =======
  1     11    1561    1572
  2      0    1572    1572
  3     37    1572    1609
  4     73    1609    1682
  5     49    1682    1731
  6      0    1731    1731
  7    310    1731    2041

Шаг 2. Выберите минимальные различия

Если все номера должны были быть выбраны, мы могли бы остановиться на шаге 1, выбирая номер пары для нечетных номеров индексы: 1, 3, 5, 7. Это правильный ответ. Однако, проблема заключается в том, что выбрано подмножество пар, что усложняет проблему совсем немного. В вашем примере должны быть выбраны 3 различия (6 чисел = 3 пары = 3 различия), которые:

• Сумма различий минимальна
• Числа, участвующие в любом выбранном различии, удаляются из списка.

Вторая точка означает, что если бы мы выбрали Diff 11 (Index = 1 выше), числа 1561 и 1572 равны удаленный из списка, и, следовательно, следующий Diff of 0 в индексе 2 не может использоваться, поскольку только 1 экземпляр из 1572. Всякий раз, когда При выборе Diff смежные значения Diff удаляются. Вот почему существует только один способ выбрать 4 пары числа из списка, содержащего восемь чисел.

Об единственном методе, который я могу придумать, чтобы свести к минимуму сумму Diff выше, - это сгенерировать и протестировать.

Следующий псевдокод описывает процесс генерации все "законные" наборы значений индекса для a DiffTable произвольного размера где выбрано произвольное число пар чисел. Один (или более) сгенерированные наборы индексов будут содержать индексы в DiffTable с минимальной суммой Diff.

/* Global Variables */
M = 7    /* Number of candidate pair differences in DiffTable */
N = 3    /* Number of indices in each candidate pair set (3 pairs of numbers) */
AllSets = [] /* Set of candidate index sets (set of sets) */

call GenIdxSet(1, []) /* Call generator with seed values */

/* AllSets now contains candidate index sets to perform min sum tests on */

end

procedure: GenIdxSet(i, IdxSet)
  /* Generate all the valid index values for current level */
  /* and subsequent levels until a complete index set is generated */
  do while i <= M
     if CountMembers(IdxSet) = N - 1 then  /* Set is complete */
        AllSets = AppendToSet(AllSets, AppendToSet(IdxSet, i))
     else                                  /* Add another index */
       call GenIdxSet(i + 2, AppendToSet(IdxSet, i))
     i = i + 1
     end
return

Функция CountMembers возвращает количество членов в заданном наборе, функция AppendToSet возвращает новый набор где аргументы добавляются в один упорядоченный набор. Например AppendToSet([a, b, c], d) возвращает набор: [a, b, c, d].

Для данных параметров M = 7 и N = 3, AllSets становится:

[[1 3 5]
 [1 3 6]  <= Diffs = (11 + 37 + 0) = 48
 [1 3 7]
 [1 4 6]
 [1 4 7]
 [1 5 7]
 [2 4 6]
 [2 4 7]
 [2 5 7]
 [3 5 7]]

Вычислить суммы, используя каждый набор индексов, тот, который минимален, определяет пары требуемых чисел в DiffTable. Выше показано, что второй набор индексов дает минимум, который вы ищете.

Это простая техника грубой силы, и она не очень хорошо масштабируется. Если у вас есть список 50 пар и хотели выбрать 5 пар, AllSets будет содержать 1 221 759 наборов число пар для проверки.

Ответ 6

Я знаю, что вы сказали, что вам не нужен код, но это лучший способ описать решение на основе набора. Решение работает под SQL Server 2008. В код включены данные для двух приведенных ниже примеров. Решение sql можно было бы сделать с помощью отдельной таблицы присоединения, но мне легче объяснить, когда есть несколько таблиц.

    --table 1 holds the values

declare @Table1 table (T1_Val int)
Insert @Table1 
--this data is test 1
--Select (1515) Union ALL
--Select (1520) Union ALL
--Select (1500) Union ALL
--Select (1535) 

--this data is test 2
Select (1731) Union ALL
Select (1572) Union ALL
Select (2041) Union ALL
Select (1561) Union ALL
Select (1682) Union ALL
Select (1572) Union ALL
Select (1609) Union ALL
Select (1731) 
--Select * from @Table1

--table 2 holds the sorted numbered list
Declare @Table2 table (T2_id int identity(1,1), T1_Val int)
Insert @Table2 Select T1_Val from @Table1 order by T1_Val

--table 3 will hold the sorted pairs
Declare @Table3 table (T3_id int identity(1,1), T21_id int, T21_Val int, T22_id int, T22_val int)
Insert @Table3
Select T2_1.T2_id, T2_1.T1_Val,T2_2.T2_id, T2_2.T1_Val from @Table2 AS T2_1
LEFT Outer join @Table2 AS T2_2 on T2_1.T2_id = T2_2.T2_id +1

--select * from @Table3
--remove odd numbered rows
delete from @Table3 where T3_id % 2 > 0 

--select * from @Table3
--show the diff values
--select *, ABS(T21_Val - T22_val) from @Table3
--show the diff values in order
--select *, ABS(T21_Val - T22_val) from @Table3 order by ABS(T21_Val - T22_val)
--display the two lowest
select TOP 2 CAST(T22_val as varchar(24)) + ' and ' + CAST(T21_val as varchar(24)) as 'The minimum difference pairs are'
, ABS(T21_Val - T22_val) as 'Difference'
from @Table3
ORDER by ABS(T21_Val - T22_val) 

Ответ 7

Я думаю, что подход @marcog может быть упрощен далее.

Возьмем базовый подход, который @jonas-kolker доказал для нахождения наименьших различий. Возьмите полученный список и отсортируйте его. Возьмите R самых маленьких записей из этого списка и используйте их в качестве отличий. Доказательство того, что это наименьшая сумма, тривиально.

@marcog эффективен O (N ^ 2), потому что R == N является законным вариантом. Этот подход должен быть (2 * (N log N)) + N aka O (N log N).

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

Ответ 8

Я бы пошел с ответом marcog, вы можете сортировать с помощью любого из сортировочных алгоритмов. Но сейчас мало что можно проанализировать.

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

Следовательно, после сортировки массива вы должны запустить внешний цикл от 0 до N-R и внутренний цикл от 0 до R-1 раз для вычисления суммы разностей.

При необходимости вы должны попробовать несколько примеров.

Ответ 9

Я применил подход, который использует рекурсивный алгоритм, но он принимает некоторые из того, что другие люди внесли.

Прежде всего мы сортируем числа:

[1561,1572,1572,1609,1682,1731,1731,2041]

Затем мы вычисляем различия, отслеживая индексы чисел, которые способствовали каждой разности:

[(11,(0,1)),(0,(1,2)),(37,(2,3)),(73,(3,4)),(49,(4,5)),(0,(5,6)),(310,(6,7))]

Итак, мы получили 11, получив разницу между числом с индексом 0 и номером в индексе 1, 37 из чисел с индексами 2 и 3.

Затем я отсортировал этот список, поэтому он сообщает мне, какие пары дают мне наименьшую разницу:

[(0,(1,2)),(0,(5,6)),(11,(0,1)),(37,(2,3)),(49,(4,5)),(73,(3,4)),(310,(6,7))]

То, что мы можем видеть здесь, состоит в том, что, учитывая, что мы хотим выбрать числа n, наивным решением может быть выбор первых n/2 элементов этого списка, Проблема в том, что в этом списке третий элемент имеет индекс с первым, поэтому мы фактически получим только 5 чисел, а не 6. В этом случае вам нужно также выбрать четвертую пару, чтобы получить набор из 6 чисел.

Отсюда я придумал этот алгоритм. Всюду есть набор принятых индексов, который начинается пустым, и осталось количество цифр, чтобы выбрать n:

• Если n равно 0, мы закончили.
• если n равно 1, а первый элемент будет содержать только один индекс, который не входит в наш набор, мы взяли первый элемент, и мы закончили.
• если n - 2 или более, а первый элемент будет содержать 2 индекса, которые не входят в наш набор, мы взяли первый элемент, и мы рекурсивно (например, goto 1). На этот раз поиск n - 2 числа, которые делают наименьшую разницу в оставшейся части списка.

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

На самом деле шаг 3 неверен (обнаружил, что как раз перед тем, как я разместил это: -/), так как нет необходимости включать раннюю разницу, чтобы покрыть индексы, которые покрываются более поздними существенными различиями. Первый пример ([1515, 1520, 1500, 1535]) не соответствует этому. Из-за этого я выбросил его в разделе ниже и расширил шаг 4, чтобы справиться с ним.

Итак, теперь мы рассмотрим особые случаи:

• ** как указано выше **
• ** как указано выше **
• Если n равно 1, но первый элемент будет содержать два индекса, мы не можем его выбрать. Мы должны отбросить этот пункт и рекурсировать. На этот раз мы все еще ищем индексы n, и никаких изменений в нашем принятом наборе не было.
• Если n - 2 или более, у нас есть выбор. Либо мы можем: а) выбрать этот элемент и повторно искать индексы n - (1 или 2), или b) пропустить этот элемент и повторно искать индексы n.

4, где это становится сложным, и где эта процедура превращается в поиск, а не только упражнение по сортировке. Как мы можем решить, какую ветку (a или b) взять? Ну, мы рекурсивные, так что позвольте обоим и посмотрите, какой из них лучше. Как мы будем судить их?

• Мы хотим, чтобы какая-либо ветвь выдавала самую низкую сумму.
• ... но только если он будет использовать правильное количество индексов.

Итак, шаг 4 становится чем-то вроде этого (псевдокод):

x       = numberOfIndicesProvidedBy(currentDifference)
branchA = findSmallestDifference (n-x, remainingDifferences) // recurse looking for **n-(1 or 2)**
branchB = findSmallestDifference (n  , remainingDifferences) // recurse looking for **n** 
sumA    = currentDifference + sumOf(branchA)
sumB    =                     sumOf(branchB) 

validA  = indicesAddedBy(branchA) == n
validB  = indicesAddedBy(branchB) == n

if not validA && not validB then return an empty branch

if validA && not validB then return branchA
if validB && not validA then return branchB

// Here, both must be valid.
if sumA <= sumB then return branchA else return branchB

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

findSmallestDifference = findSmallestDifference' Set.empty

findSmallestDifference' _     _ [] = []
findSmallestDifference' taken n (d:ds)
    | n == 0                = []    -- Case 1
    | n == 1 && provides1 d = [d]   -- Case 2
    | n == 1 && provides2 d = findSmallestDifference' taken n ds -- Case 3
    | provides0 d           = findSmallestDifference' taken n ds -- Case 3a (See Edit)
    | validA && not validB             = branchA -- Case 4
    | validB && not validA             = branchB -- Case 4
    | validA && validB && sumA <= sumB = branchA -- Case 4
    | validA && validB && sumB <= sumA = branchB -- Case 4
    | otherwise             = []                 -- Case 4
        where branchA = d : findSmallestDifference' (newTaken d) (n - (provides taken d)) ds
              branchB = findSmallestDifference' taken n ds
              sumA    = sumDifferences branchA
              sumB    = sumDifferences branchB
              validA  = n == (indicesTaken branchA)
              validB  = n == (indicesTaken branchA)
              newTaken x = insertIndices x taken 

Надеюсь, вы увидите все случаи там. Этот код (-ish), плюс некоторые обертки производит это:

*Main> findLeastDiff 6 [1731, 1572, 2041, 1561, 1682, 1572, 1609, 1731]
Smallest Difference found is 48
      1572 -   1572 =      0
      1731 -   1731 =      0
      1572 -   1561 =     11
      1609 -   1572 =     37
*Main> findLeastDiff 4 [1515, 1520, 1500,1535]
Smallest Difference found is 30
      1515 -   1500 =     15
      1535 -   1520 =     15

Это стало длинным, но я попытался быть явным. Надеюсь, это стоило того.

Изменить. Существует случай 3a, который можно добавить, чтобы избежать ненужной работы. Если текущая разница не содержит дополнительных индексов, ее можно пропустить. Об этом говорится в пункте 4 выше, но нет смысла оценивать обе половины дерева без усиления. Я добавил это к Haskell.

Ответ 10

Что-то вроде

• Список сортировки
• Найти дубликаты
• Сделайте дубликаты пары
• удалить дубликаты из списка
• перерыв остатка списка в пары
• рассчитать разницу в каждой паре
• принимать самые низкие суммы

В вашем примере у вас есть 8 номеров и вам нужны лучшие 3 пары. Сначала соберите список, который дает вам

1561, 1572, 1572, 1609, 1682, 1731, 1731, 2041

Если у вас есть дубликаты, сделайте их пару и удалите их из списка, чтобы у вас

[1572, 1572] = 0
[1731, 1731] = 0
L = { 1561, 1609, 1682, 2041 }

Разделите оставшийся список на пары, предоставив вам следующие 4 пары

[1572, 1572] = 0
[1731, 1731] = 0
[1561, 1609] = 48
[1682, 2041] = 359

Затем отбросьте количество цифр, которое вам нужно.

Это дает вам следующие 3 пары с наименьшими парами

[1572, 1572] = 0
[1731, 1731] = 0
[1561, 1609] = 48

Итак,

0 + 0 + 48 = 48