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

Принимая во внимание правку:

Начните с сортировки списка. Затем используйте решение динамического программирования, с состоянием i, n , представляющее минимальную сумму N разностей при рассмотрении только первых i чисел в последовательности. Начальные состояния: dp[*][0] = 0, все остальное = бесконечность. Используйте два цикла: внешний цикл, проходящий через i от 1 до N, внутренний цикл, проходящий через n от 0 до R (3 в вашем примере edit-используется 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) пространство.

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

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

• сортировка чисел
• испускаем (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 должно быть сопряжено со вторым наименьшим числом; по индукции в остальной части списка сопряжение наименьших соседей всегда оптимально, поэтому предложенный мной алгоритм верен.

Упорядочьте список, затем выполните вычисление разницы.

EDIT: hi @hey

Эту задачу можно решить с помощью динамического программирования.

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

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

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

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

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

1. Лучший(1, L) = наименьший (L)
2. best (2, L) = smallest2 (L)
3. для i от 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

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

(коммутационная работа выполняется smallest2)

Шаг 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 (индекс = 1 выше), числа 1561 и 1572 являются удален из списка, и, следовательно, следующий Diff из 0 по индексу 2 не может быть использован, потому что только 1 экземпляр из 1572 осталось. Всякий раз, когда a Diff выбирается смежное Diff значение снимаются. Вот почему есть только один способ выбрать 4 пары числа из списка, содержащего восемь чисел.

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

Следующий псевдокод описывает процесс для генерации все "законные" наборы значений индекса для 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, Все множества становятся:

[[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 наборов количество пар для тестирования.

Я знаю, что вы сказали, что вам не нужен код, но это лучший способ для меня описать решение, основанное на множестве. Решение работает под управлением 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) 

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

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

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

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

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

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

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

Если нужно, вы должны попробовать с некоторыми примерами.

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

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

[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 :

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

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

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

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

1. * * как указано выше * *
2. * * как указано выше * *
3. Если n равно 1, но первый элемент будет содержать два индекса, мы не можем его выбрать. Мы должны выбросить этот предмет и рекурсировать. На этот раз мы все еще ищем N индексов, и никаких изменений не произошло к нашему набору.
4. Если n равно 2 или более, у нас есть выбор. Либо мы можем а) выбрать этот пункт и рекурсивно искать n - (1 или 2) индексы, либо б) пропустить этот пункт и рекурсивно искать 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

[6] это стало долгим,но я постарался быть ясным. Надеюсь, это того стоило.

---

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

Что-то вроде

1. Список Сортировки
2. Найти Дубликаты
3. Сделайте дубликаты парой
4. удалить дубликаты из списка
5. разбить остальную часть списка на пары
6. вычислить различия каждой пары
7. Возьмите наименьшее количество

В вашем примере у вас есть 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