Подпоследовательность с минимальной абсолютной величиной

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

Это похоже на проблему DP.

  • Пусть S1[i] - подпоследовательность, заканчивающаяся на a[i], для которой своя суммa > 0 и абс (сумма) минимизированы.

  • Пусть S2[i] - подпоследовательность, заканчивающаяся на a[i], для которой его сумма < 0 и абс (сумма) минимизированы.

  • S1[i] - это минимум для всех S1[j] + a[i] для j < i, если S1[j] + a[i] > 0 && < t21 < 0

  • S2[i] является минимумом всех S2[j] + a[i] для j < i, если S2[j] + a[i] < 0 && a[i] > 0

Как только мы теперь S1[i] и S2[i] для всех индексов легко найти подпоследовательность с минимальным абсолютным значением своих элементов.

Имеет ли смысл?

3 ответа

Я принимаю непустые результирующие множества.

Пусть список целых чисел равен S. Рассмотрим наименьшее значение absolute среди них S [k]. Если S [K] == 0 вернет его. Иначе цель состоит в том, чтобы найти значение меньше, чем S [K].

Разделите целые числа на два набора положительных и отрицательных целых чисел, как вы упомянули SP (неотрицательный) и SN. Теперь найдите сумму в SP, которая близка к другой сумме в SN меньше, чем S [K]. Это можно сделать, сортируя элементы в SP и SN отдельно по абсолютным значениям, сохраняя в каждом списке сумму и указатель на голову. Вы можете заполнить детали.

Это может дать что-то меньшее, чем S [K], иначе отчет S [K].

Например: S = {1, -4, 2, -8, 5, -7} k = 0, S [k] = 1

SP (отсортировано) = {1, 2, 5} SN (отсортировано) = {-4, -7, -8}

Одновременно перемещая два массива, вы можете получить некоторые кандидаты {1,2} и {-4}, которые дадут тот же результат, что и S [k]. но {2,5} и {-7} будут лучше давать чистую сумму 0.


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

Так как порядок элементов не имеет значения, ваш вопрос просто спрашивает: учитывая (мульти) набор элементов, какова минимальная абсолютная сумма среди всех подмножеств. Легко видеть, что проблема подмножества сумм сводится к этой проблеме. Так как сумма подмножеств NP-жесткая, то и эта проблема. Поэтому неплохо, что ваш алгоритм полиномиального времени неверен. В противном случае P = NP.

Фактически, контрпример к вашему алгоритму является входной последовательностью {-1, 2, -2}.

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


Хотелось бы, чтобы я мог следовать вашим рассуждениям, но я немного замедлил... и вы попросили DP, а здесь Haskell снова... но это вы имеете в виду?

import Data.List (sortBy, subsequences)
import Data.Ord (comparing)
minValSub xs = 
 head $ sortBy (comparing snd) 
 $ map (\x -> (x, abs (sum x)) ) (filter (not . null) $ subsequences xs)
OUTPUT:
*Main> minValSub [1,2,3,-4,5]
([1,3,-4],0)

licensed under cc by-sa 3.0 with attribution.