Я задал этот вопрос на StackOverflow , но я думаю, что это более подходящее место.
Это проблема из курса Введение в алгоритмы :
У вас есть массив с положительными целыми числами (массив не нужно сортировать или элементы уникальны). Предложите алгоритм , чтобы найти наибольшую сумму элементов, которая делится на .
Пример: . Ответ (с элементами )
Относительно легко найти его в используя динамическое программирование и сохраняя наибольшую сумму с остатком .
Кроме того, если мы ограничим внимание последовательной последовательностью элементов, легко найти оптимальную такую последовательность за времени, сохраняя частичные суммы по модулю : let , для каждого остатка запомните наибольший индекстакой чтоS [j] \ эквивалента r \ pmod {n}, а затем для каждогоiрассмотримS [j] -S [i],гдеjиндекс, соответствующий .
Но есть ли -временное решение для общего случая? Любые предложения будут оценены! Я считаю, что это имеет отношение к линейной алгебре, но я не уверен, что именно.
Или же это можно сделать за ?
источник
Ответы:
Вот несколько случайных идей:
Алгоритм динамического программирования можно перевернуть, чтобы найти наименьшую сумму вместо самой большой суммы. В итоге вы просто ищете сумму, равную остатку от суммы всего массива, а не одну равную нулю. Если мы обрабатываем элементы в порядке возрастания, это иногда позволяет динамическому алгоритму завершить работу перед обработкой всего массива.
Стоимость была бы если бы мы обработали k элементов. В этом алгоритме нет нижней границы Ω ( n log n ) , потому что нам не нужно сортировать все элементы. Требуется только O ( n log k ), чтобы получить k наименьших элементов.O ( n k ) К Ω ( n logн ) O ( n logк ) К
Если бы мы заботились о наборе с размером larget, а не о наборе с наибольшей суммой, мы могли бы использовать умножение на основе быстрого фурье-преобразования для решения задачи в время. Аналогично тому, что сделано в 3SUM, когда диапазон доменов ограничен. (Примечание: используйте повторный квадрат для выполнения двоичного поиска, иначе вы получите O ( n k ( log n ) ( log log n ) ), где kO ( n ( журнал)н )2( журналжурналн ) ) O ( n k ( logn ) ( журналжурналн ) ) К количество пропущенных элементов.)
Когда составное, а почти все остатки кратны одному из факторов n , можно сэкономить значительное время, сосредоточив внимание на остатках, не кратных этому фактору.N N
Когда остаток
r
встречается очень часто или присутствуют только несколько остатков, отслеживание информации «следующий открытый слот, если вы начинаете отсюда и продолжаете продвигаться поr
», может сэкономить много сканирований для прыжков в открытые места. время.Вы можете уменьшить логарифмический коэффициент , только отслеживая достижимость и используя битовые маски (в динамическом алгоритме с переворачиванием), а затем возвращаясь назад, когда достигнете целевого остатка.
Алгоритм динамического программирования очень удобен для параллельной работы. С процессором для каждого слота буфера вы можете перейти к . В качестве альтернативы, используя O ( n 2 ) широту и разделяя и завоевывая агрегацию вместо итеративного агрегирования, стоимость глубины канала может доходить до O ( log 2 n ) .O ( n ) O ( n2) O ( журнал2н )
(Мета) Я сильно подозреваю, что проблема, которую вам дали, связана с непрерывными суммами. Если вы связались с реальной проблемой, это было бы легко проверить. В противном случае я очень удивлен тем, насколько сложна эта проблема, учитывая, что она была задана в курсе под названием «Введение в алгоритмы». Но, может быть, вы рассмотрели трюк в классе, который делает его тривиальным.
источник
Мой предложенный алгоритм выглядит следующим образом:
Сумма делится на n, если вы добавляете только слагаемые, кратные n.
Перед началом вы создаете хэш-карту с int в качестве ключа и списком индексов в качестве значения. Вы также создаете список результатов, содержащий индексы.
Затем вы перебираете массив и добавляете каждый индекс, у которого mod n равен нулю, в ваш список результатов. Для каждого другого индекса вы делаете следующее:
Вы вычитаете значение mod n этого индекса из n. Этот результат является ключом для вашей хэш-карты, в которой хранятся индексы для элементов с требуемым значением. Теперь вы добавляете этот индекс в список в hashmap и двигаетесь дальше.
После того, как вы закончили цикл по массиву, вы вычисляете вывод. Вы делаете это путем сортировки каждого списка в хэш-карте в соответствии со значением, на которое указывает индекс. Теперь вы рассматриваете каждую пару в хэш-карте, суммирующую до n. Поэтому, если n = 7, вы ищите в хэш-карте 3 и 4. Если вы получили запись в обоих, вы берете два самых больших значения, удаляете их из своих списков и добавляете их в свой список результатов.
Последняя рекомендация: по-прежнему не тестируйте алгоритм, напишите тестовый сценарий для него, используя алгоритм перебора.
источник
используйте этот метод DP из ( /programming/4487438/maximum-sum-of-non-consecutive-elements?rq=1 ):
Для данного массива A [0..n] пусть M (i) будет оптимальным решением с использованием элементов с индексами 0..i. Тогда M (-1) = 0 (используется в повторении), M (0) = A [0] и M (i) = max (M (i - 1), M (i - 2) + A [i ]) для i = 1, ..., n. M (n) - решение, которое мы хотим. Это O (n) . Вы можете использовать другой массив для хранения того, какой выбор сделан для каждой подзадачи, и таким образом восстановить фактические выбранные элементы.
Измените рекурсию на M (i) = max (M (i - 1), M (i - 2) + A [i]) так, чтобы она сохранялась, только если она делится на N
источник