Наибольшая сумма, делимая на n

16

Я задал этот вопрос на StackOverflow , но я думаю, что это более подходящее место.

Это проблема из курса Введение в алгоритмы :

У вас есть массив с положительными целыми числами (массив не нужно сортировать или элементы уникальны). Предложите алгоритм , чтобы найти наибольшую сумму элементов, которая делится на .anO(n)n

Пример: . Ответ (с элементами )a=[6,1,13,4,9,8,25],n=7566,13,4,8,25

Относительно легко найти его в используя динамическое программирование и сохраняя наибольшую сумму с остатком .O(n2)0,1,2,...,n1

Кроме того, если мы ограничим внимание последовательной последовательностью элементов, легко найти оптимальную такую ​​последовательность за времени, сохраняя частичные суммы по модулюO(n)n : letS[i]=a[0]+a[1]++a[i] , для каждого остаткаr запомните наибольший индекстакой чтоS [j] \ эквивалента r \ pmod {n}, а затем для каждогоiрассмотримS [j] -S [i],гдеjиндекс, соответствующийjS[j]r(modn)iS[j]S[i]jr=S[i]modn .

Но есть ли -временное решение для общего случая? Любые предложения будут оценены! Я считаю, что это имеет отношение к линейной алгебре, но я не уверен, что именно.O(n)

Или же это можно сделать за ?O(nlogn)

дельта-терминатор
источник
2
1. Вы разместили точно такой же вопрос на переполнение стека. Пожалуйста , не размещайте один и тот же вопрос на нескольких сайтах . Мы не хотим, чтобы несколько копий распространялись на нескольких сайтах SE. Если вы не получили приемлемый ответ, можно пометить ваш вопрос для перехода на другой сайт, но не размещайте то же самое в другом месте. 2. Можете ли вы дать ссылку / цитату / ссылку на учебник или курс, где он появился? Насколько вы уверены, что существует -временное решение? O(n)
DW
5
Вызов в вашем университете все еще открыт? Было бы очень полезно увидеть ссылку на курс, точный вопрос, и если это действительно и люди, которые его подготовили, объяснят / опубликуют свой ответ, это было бы здорово. O(n)
Зло
Относительно легко найти его в O (n2) O (n2), используя динамическое программирование и сохраняя наибольшую сумму с остатком 0,1,2, ..., n − 10,1,2, ..., n − 1. Не могли бы вы уточнить это немного? Я могу понять, как это будет n-квадрат, если мы рассмотрим только смежные элементы, но также и с несмежными элементами, разве это не будет экспоненциальным по порядку?
Nithish Inpursuit Ofhappiness

Ответы:

4

Вот несколько случайных идей:

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

    Стоимость была бы если бы мы обработали k элементов. В этом алгоритме нет нижней границы Ω ( n log n ) , потому что нам не нужно сортировать все элементы. Требуется только O ( n log k ), чтобы получить k наименьших элементов.О(NК)КΩ(NжурналN)О(NжурналК)К

  • Если бы мы заботились о наборе с размером larget, а не о наборе с наибольшей суммой, мы могли бы использовать умножение на основе быстрого фурье-преобразования для решения задачи в время. Аналогично тому, что сделано в 3SUM, когда диапазон доменов ограничен. (Примечание: используйте повторный квадрат для выполнения двоичного поиска, иначе вы получите O ( n k ( log n ) ( log log n ) ), где kО(N(журналN)2(журналжурналN))О(NК(журналN)(журналжурналN))К количество пропущенных элементов.)

  • Когда составное, а почти все остатки кратны одному из факторов n , можно сэкономить значительное время, сосредоточив внимание на остатках, не кратных этому фактору.NN

  • Когда остаток rвстречается очень часто или присутствуют только несколько остатков, отслеживание информации «следующий открытый слот, если вы начинаете отсюда и продолжаете продвигаться по r», может сэкономить много сканирований для прыжков в открытые места. время.

  • Вы можете уменьшить логарифмический коэффициент , только отслеживая достижимость и используя битовые маски (в динамическом алгоритме с переворачиванием), а затем возвращаясь назад, когда достигнете целевого остатка.

  • Алгоритм динамического программирования очень удобен для параллельной работы. С процессором для каждого слота буфера вы можете перейти к . В качестве альтернативы, используя O ( n 2 ) широту и разделяя и завоевывая агрегацию вместо итеративного агрегирования, стоимость глубины канала может доходить до O ( log 2 n ) .О(N)О(N2)О(журнал2N)

  • (Мета) Я сильно подозреваю, что проблема, которую вам дали, связана с непрерывными суммами. Если вы связались с реальной проблемой, это было бы легко проверить. В противном случае я очень удивлен тем, насколько сложна эта проблема, учитывая, что она была задана в курсе под названием «Введение в алгоритмы». Но, может быть, вы рассмотрели трюк в классе, который делает его тривиальным.

Крейг Гидни
источник
Для начала. Это не написано в спецификациях проблемы, поэтому вы не можете этого допустить. Кроме того, проблема не в том, что вы не можете изменить массив или создать новые, вы действительно можете. Единственное, что вам нужно сделать, это найти числа, которые суммируются, дают вам наибольшую сумму, которая делится на в O ( n ) сложности времени (обычно это предполагается только сложность времени). NО(N)
Nbro
2
@EvilJS Подмножество с наибольшей суммой с остатком 0 равно полному набору после удаления подмножества с наименьшей суммой с остатком, совпадающим с суммой полного набора. Поиск наименьшей суммы, конгруэнтной , более удобен, чем поиск наименьшей суммы, конгруэнтной r 2, поскольку она позволяет завершить работу, как только вы найдете решение (при обработке элементов в возрастающем порядке), вместо того, чтобы продолжать. р1р2
Крейг Гидни
-1

Мой предложенный алгоритм выглядит следующим образом:

Сумма делится на n, если вы добавляете только слагаемые, кратные n.

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

Затем вы перебираете массив и добавляете каждый индекс, у которого mod n равен нулю, в ваш список результатов. Для каждого другого индекса вы делаете следующее:

Вы вычитаете значение mod n этого индекса из n. Этот результат является ключом для вашей хэш-карты, в которой хранятся индексы для элементов с требуемым значением. Теперь вы добавляете этот индекс в список в hashmap и двигаетесь дальше.

После того, как вы закончили цикл по массиву, вы вычисляете вывод. Вы делаете это путем сортировки каждого списка в хэш-карте в соответствии со значением, на которое указывает индекс. Теперь вы рассматриваете каждую пару в хэш-карте, суммирующую до n. Поэтому, если n = 7, вы ищите в хэш-карте 3 и 4. Если вы получили запись в обоих, вы берете два самых больших значения, удаляете их из своих списков и добавляете их в свой список результатов.

Последняя рекомендация: по-прежнему не тестируйте алгоритм, напишите тестовый сценарий для него, используя алгоритм перебора.

Тобиас Вюрфль
источник
2
Жадный, линейный, не работает. Вы рассматриваете только элементы, которые делятся на n, а пары делятся на n, как насчет троек и других? Это не гарантирует максимальную сумму подмножества в тривиальном случае. [2, 1, 8] -> максимальная сумма равна 9, но ваш алгоритм возвращает 3.
Зло
N2
Спасибо, что указали мне на эту ошибку. Моя идея по улучшению заключается в том, чтобы создать хэш-карту из стеков списков, упорядоченных по возрастанию значения и начать накапливать только после завершения прохода через массив.
Тобиас Вюрфль
Вы имеете в виду массив массивов, которые будут отсортированы, и "hashmap" равен% n? Вам все еще нужно отсортировать их, и если они отсортированы, то брать минимальное / максимальное значение можно, но все же есть неотъемлемая часть фактического выбора подмножества, что в худшем случае не приносит пользы. Во всяком случае, если у вас есть некоторые улучшения, может быть, вы могли бы редактировать пост?
Зло
Да, это была довольно быстрая идея со стеками. На самом деле вам нужны только списки в хэш-карте, которую вы сортируете. Я не был уверен, вежливо ли редактировать мой первый ответ. В конце концов, я допустил ошибку в своей первой попытке.
Тобиас Вюрфль
-2

используйте этот метод 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

тупица
источник
2
Это не работает - я дам вам понять, почему. (Подсказка: попробуйте запустить его на массиве констант 1.) Кроме того, в этой задаче мы разрешаем последовательные элементы.
Ювал Фильмус
1
Это очень хорошее решение, просто для совершенно другой (и гораздо более простой) проблемы.
Зло