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

Question

Я должен найти минимально возможную сумму из разности чисел.

Допустим, у меня есть 4 номера. 1515, 1520, 1500 и 1535. Наименьшая сумма разницы составляет 30, потому что 1535 - 1520 = 15 && 1515 - 1500 = 15 и 15 + 15 = 30. Если бы я сделал так: 1520 - 1515 = 5 && 1535 - 1500 = 35 было бы 40 в сумме.

Надеюсь, ты понял, если нет, спроси меня.

Есть идеи, как это запрограммировать? Я только что нашел это в Интернете, пытался перевести с моего языка на английский. Звучит интересно. Я не могу сделать брутфорс, потому что для компиляции потребуются годы. Мне не нужен код, просто идеи, как программировать или небольшой фрагмент кода.

Спасибо.

Edit: Я не все опубликовал ... Еще одно издание:

У меня есть, скажем, 8 возможных чисел. Но мне нужно взять только 6 из них, чтобы получить наименьшую сумму. Например, числа 1731, 1572, 2041, 1561, 1682, 1572, 1609, 1731, наименьшая сумма будет 48, но здесь я должен взять только 6 чисел из 8.

Answer 1

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

Доказательство

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

Заявка : оптимальное решение всегда состоит из различий последовательных элементов.
Доказательство : Предположим, вы исправили подмножество элементов, различия которых взяты. Тогда, согласно доказательству , приведенному Йонасом Кёлькером , оптимальное решение только для этого подмножества состоит из отличий последовательных элементов из списка. Теперь предположим, что существует решение, соответствующее подмножеству, которое не содержит пар последовательных элементов, то есть решение включает в себя разность x _j -x _i , где j> i + 1. Затем мы можем заменить x _j на x _{i + 1} , чтобы получить меньшую разницу, поскольку
x _i ≤ x _{i + 1} ≤ x _j ⇒ x _{i + 1} -x _i ≤ x _J -х _я .
(Излишне говорить, что если x _{i + 1} = x _j , то взятие x _{i + 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

Answer 2

Принимая во внимание редактирование:

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

Answer 3

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

Answer 4

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

РЕДАКТИРОВАТЬ: hi @ hey

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

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

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

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

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

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

1. best (1, L) = наименьший (L)
2. лучший (2, L) = наименьший2 (L)
3. для i от 1 до k:

loop

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)

Answer 5

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

Answer 6

Шаг 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 осталось. Всякий раз, когда 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, 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 наборов число пар для тестирования.

Answer 7

Что-то вроде

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

Answer 8

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

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

[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 индекса, которых нет в нашем наборе, мы взяли первый элемент и рекурсивно (например, перейдем к 1). На этот раз ищем n - 2 числа, которые имеют наименьшую разницу в остальной части списка.

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

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

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

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

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

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

Таким образом, шаг 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

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

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

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

---

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

Answer 9

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

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

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

При необходимости попробуйте несколько примеров.

Answer 10

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

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

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

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