Как максимизировать сумму элементов выбираемых из списка?
Дан список натуральных положительных.
Из списка можно выбрать некоторое количество элементов, таким образом, чтобы разность индексов элементов идущих подряд была не менее K.
Необходимо максимизировать сумму выбираемых элементов.
К примеру дан список:
7, 18, 6, 10, 12, 128
И K == 3. В этом случае ответом будет набор элементов 1,5 значения которых 18 и 128 соответственно.
При этом идея о том что нужно сначала выбрать максимальный элемент, а потом от него плясать не подходит.
К примеру рассмотрим такой массив при том же K:
19, 20, 1, 17, 1, 1, 17, 1
Если выбрать элемент 1(20), то следующим доступным будет элемент 6(17), так как элемент 3 выбрать уже нельзя, так как разница индексов меньше K (3-1 < K) и сумма этих элементов == 37.
Но если выбрать не максимум - 0(19), то можно получить комбинация 0,3,6 - разность индексов не больше K, а сумма 53 - всяко больше 37
Какие есть идеи? Время поиска комбинаций важно - списки длинные.
Похоже на модификацию задачи о рюкзаке. Если это так, то со временем поиска всё будет плохо, потому что задача NP-полная. Хотя возможно, что и получиться, ведь ограничения на сумму сверху нет.
Рекомендую посмотреть в сторону метода ветвей и границ.
В общем, примерный план решения такой:
Начинаем смотреть элементы с конца списка. Последние k элементов заносятся в кэш как есть, от них никуда не деться. Далее для каждого элемента с номером i нужно просмотреть, как он сочетается с элементами i + k .. i + 2k. Дальше смотреть смысла нет, так как это только ухудшит ситуацию. И так идём до первого элемента. Потом выбираем лучший из элементов с номерами 1 .. k. Вроде как получается линейный относительно размера списка код (не более k(n + 1) операций).
Код реализации: https://ideone.com/ZU8Mrr
Похоже ваш код работает, но я по правде говоря не могу въехать в реализацию.
Последние k элементов заносятся в кэш как есть, от них никуда не деться.
В какой кэш? Что он нам даёт? Как мы его используем и почему последние k элементов должны попасть туда в начале?
Далее для каждого элемента с номером i нужно просмотреть, как он сочетается с элементами i + k .. i + 2k
Вы имеете ввиду найти в диапазоне от i+k до i+2k наилучшую для него пару? И что? Записать для этого элемента индекс наилучшей пары? Предположим.
И так идём до первого элемента. Потом выбираем лучший из элементов с номерами 1 .. k
А почему я тогда не могу начать с начала и выбрав максимум на отрезке 1..k подбирать наилучшую пару для него? На отрезке k..2k?
В смысле чем такой подход отличается от вашего предложения не могу уловить...
В какой кэш? Что он нам даёт? Как мы его используем и почему последние k элементов должны попасть туда в начале?
Если не кэшировать результаты работы, вычислительная сложность растёт катастрофически. В кэш для каждого номера элемента заносится список номеров элементов, с которыми он образует цепочку с самой большой суммой (и сама сумма, чтобы по 100 раз её не пересчитывать). Идём с конца, потому что так удобнее реализовывать добавление элементов в список. Можно и с начала, на самом деле.
Вы имеете ввиду найти в диапазоне от i+k до i+2k наилучшую для него пару? И что? Записать для этого элемента индекс наилучшей пары? Предположим.
Ага, только не пары, а всю цепочку, так удобнее.
А почему я тогда не могу начать с начала и выбрав максимум на отрезке 1..k подбирать наилучшую пару для него? На отрезке k..2k?
В смысле чем такой подход отличается от вашего предложения не могу уловить...
Потому что если мы начнём с начала, то элементы k..2k ещё не будут посчитаны, их надо заносить в очередь на расчёт, организовывать рекурсию или цикл... В общем, с конца просто удобнее.
Более формальное описание алгоритма:
0) входные данные: l — список положительных чисел длиной n, k — число (минимальное расстояние до соседа), c — пустой ассоциативный массив (хэш-таблица, время поиска элемента O(1)).
Элемент c[i] будет содержать в себе значения максимальной суммы (c[i].sum), которую можно получить из среза списка l с элемента i и до конца, а также номера элементов, участвующие в формировании данной суммы (c[i].list).
1) пусть i — число, равное (n + 1);
2) установим i ← i - 1;
3) если i больше или равно (n - k), то установим c[i] ← (l[i], i) и перейдём к шагу (2);
4) если i равно 0, перейдём к шагу (7);
5) пусть t — максимум из (l[i] + c[i + j].sum), где j лежит в диапазоне от k до 2k (тут может быть выход за границы массива, это надо учесть), пусть j' — такое j, при котором достигается максимум;
брать j меньше k мы не можем, так как это ограничено условием задачи, брать j больше 2k мы не можем, так как для любого положительного a сумма l[i] + l[i + 2k + a] будет меньше, чем l[i] + l[i + k] + l[i + 2k + a];
6) установим c[i] ← (t, i & c[i + j'].list) (& — конкатенация списков) и перейдём к шагу (2);
7) теперь у нас полностью заполнен кэш, можем искать решение, для этого выберем начальный элемент b в диапазоне от 1 до k, который обеспечивает максимальное значение c[b].sum; c[b].list — искомое решение.
Роман Румянцев, спасибо, но я уже сам размотал вашу идею. Это похоже на решение, и на тестовых данных у меня работает. Но не проходит онлайн проверку, не понятно на каком наборе данных :(
https://pastebin.com/UNK772g0 - вот реализация всей задачи. Конкретно вынесенное в вопрос сюда это блок начиная с
# =========================================================================================
Вот запуск на тестовых данных и промежуточные результаты:
Здесь:
def - просматриваемый массив
maxDef - индекс максимум в скользящем окне 3, для окна начинающегося в i
best next и summ - то что вы называете кэшем:
Первый содержит индекс наиболее подходящего элемента для элемента i
второй собственно суммы.
Если интересно вся задача здесь: https://informatics.mccme.ru/moodle/mod/statements...
Правда решаем на Python и дочка только учит, а для меня язык не родной, поэтому наверно что-то в реализации может быть коряво написано - прошу простить за такое.
Сейчас пробую составить свои наборы данных и потестить ещё
Роман Румянцев, нашёл как минимум одну ошибку в коде который описал выше - проблема была тут:
тут может быть выход за границы массива, это надо учесть
Я это сделал оригинальным образом - нарастил массив maxDef содержащий максимумы в окнах последним элементом, что конечно не правильно - правильным было нарастить исходный массив k-1 нулем, чтобы создать последнее псевдоокно, состоящее из 1 последнего элемента и нолей свисающих за край массива.
Александр Маджугин, ага, решение неправильное, должно быть 379 (1-5-8-11). Проверьте, везде ли правильно выбраны типы интервалов (включена или нет правая и левая границы). Похоже, что вы пропускаете последний элемент. Возможно, проблема в строке 125, там, вероятно, нужно писать так (но я не уверен): for i in range(len(defA) - 2*k + 1, -1, -1):
И заодно при этом добавить ещё 1 ноль в основной список, чтобы выхода за границу не было.
PS
Оптимизированный по производительности вариант моего кода: https://ideone.com/tCl2WO (больше функциональности богу функциональности, обрабатывает миллион элементов за секунду)
И то же самое на Python: https://ideone.com/5M9dKK
Роман Румянцев, спасибо за реализацию - познакомился с лямбдами (пришлось звать дочь для объяснения).
Кстати как минимум в пайтоновской реализации есть проблемка, из-за которого в результат могут попадать элемент за пределами списка. Вместо if next < 0 нужно использовать if next < 0 or next > len(data):
Но увы - программа теперь не проходит по скорости - сыплетася на больших k - всё из-за max() для скользящего отрезка. Попробую избавится от этого недостастака
Роман Румянцев, добавляем скорости богу функциональности: https://pastebin.com/jEWsBThL
Довел ваше решение - теперь никакого max в цикле - для поиска максимума используем дек.
Правда дек самописный.
Это по двум причинам:
1 Я показывал дочери как реализовать дек вообще и как сделать его быстрым игонрируя расход памяти.
2 Я просто ничего не знал про модуль collections :\
Задача решена и сдана. Интересно что в целом (не эта последняя часть) решение поулчилось оч. многословное (я вижу где у неё проблемы и можно убрать один лишний прогон), но в сети гуглятся решения, которые сделаны вообще за один единственный прогон и люди жалуются что решения эти не проходят по времени...
Главный вывод - задач всё же решается за линейное время. Огромное спасибо за помощь.
А есть-ли ограничения на количество элементов в списке? Если есть - я бы сделал так: Построил бы все комбинации из допустимого количества элементов, просчитав при этом их суммы. Потом бы отсортировал эти объекты по спаданию суммы, а потом начиная с наибольшей суммы проверял-бы удовлетворяется-ли условие по К. (это очень просто). Как только условие удовлетворено - максимально возможная сумма найдена.
Но если вдруг указанного ограничения нет - то увы, возвращаемся опять к NP-сложной задаче.
Я имел ввиду, на ограничения количества элементов, из которых составляется сумма. Если нет - то все очень не радужно. Метод "ветвей и границ" точного решения не гарантирует.
Надеюсь, про O(n) это вы пошутили.
А если "есть основание", то хотелось бы его услышать.
И есть основание полагать, что имеет решение со сложностью O(n)
в один проход? Возможно и есть, например динамическим программированием, ценой расходов памяти, храня промежуточные результаты в матрице и оптимизируя очередью или стеком.
И есть основание полагать, что имеет решение со сложностью O(n)
Александр Маджугин, для каждого выбранного элемента мы должны проверить все элементы после него, так что в лучшем случае O(n·log n) по времени и O(n) по памяти (для каждого кэшированного элемента хранится следующий оптимальный, в кэш для 1 элемента лезем несколько раз) или O(n) по времени и O(n·log n) по памяти (для каждого кэшированного элемента хранится вся цепочка оптимальных, в кэш для 1 элемента лезем 1 раз).
PS Если нужна только максимальная сумма, без способа её получения, то можно и в O(n) уложиться.
Я имел ввиду, на ограничения количества элементов, из которых составляется сумма. Если нет - то все очень не радужно. Метод "ветвей и границ" точного решения не гарантирует.
Нет - ограничения нет. Количество элементов может быть любым.
Надеюсь, про O(n) это вы пошутили.
Я серьёзен как никогда - с этой задачей пришла дочь, а я не могу справится. Задача из раздела который называется "Линейные алгоритмы", что как бы намекает.
На самом деле задачка там сильно посложнее, но в итоге легко за линейное время сводится вот этой и дальше понять не могу чего делать.
Не факт, что в один. Там у меня до этого еще несколько вычислений, которые уже делают 3 прохода, но там всегда три прохода (можно свести к двум, но сейчас не это важно) и от n не зависит.
храня промежуточные результаты в матрице и оптимизируя очередью или стеком.
Возможно деком - уже дек активно юзаю чтобы свести задачу к этой.
Когда ваша дочь принесет домой ответ от своего преподавателя - будьте добры, поделитесь ним с нами. А то очень интересно стало. Переборный алгоритм за линейное время?! Будем очень благодарны.
dmshar, я там в другом варианте ответа в комментах описал свой вариант формально. Алгоритм вроде как линейный по размеру списка чисел (число операций порядка K*(n + 1)), затраты памяти ориентировочно O(n*log n).
Нужно создать дополнительный список B и заполнить его так, чтобы в ячейке B[I] находилась максимальная возможная сумма элементов A[0..I]
Если список состоит из 1 элемента, то ответом будет сам элемент
Если 2 элемента, то для I=1 это будет max(B[0], А[1])
Если 3 элемента, а K = 1, то для I=2 ответ будет max(B[1], A[2] + B[0])
Это стандартная задача на динамическое программирование. Например заведите f(i) - максимальная сумма, которую можно получить взяв какие-то из первых i элементов.
Пересчет: f(i) = max(f(i-1), a[i-1] + f(i-k)) - тут мы или не берем последний элемент, и тогда ответ f(i-1) или берем - и тогда мы обязаны пропустить k-1 следующих элементов. База: f(i<=0) = 0.
Можно сократить потребление памяти если считать в массиве снизу вверх и хранить только последние k элементов f[].
1.Сначала сплитим поток с наивысшей частотой (K=>min) на несколько групп в рамках одного минимального периода (K) и ищем наибольшую сумму в каждой такой группе:
7, 10
18, 12
6, 128 (наибольшая сумма)
3.Повторяем всё тоже самое с найденного места опять с минимальным K, постепенно увеличивая его до размера найденного расстояния в предыдущем шаге.
И так до тех пор, пока не закончится весь входной поток значений.
Александр Маджугин, я имел ввиду этот листинг.
Линейный - это когда в худшем случае количество любых смещений при переборе элементов списка не превышает количества элементов этого списка. Здесь - требуется смещений больше, чем элементов в списке (кмк).
xmoonlight, нет - эти алгоритмы линейные.
Точнее в первом листинге https://ideone.com/ZU8Mrr на самом деле есть неленейность (насколько я его могу понять), но она скрыта внутри встроенных функций, а не в самом алгоритме.
Если мы возмём понятный мне аналог на питоне, который есть ниже, то там есть функция max() которая не линейная. Это так.
Но последняя реализация моя линейная так как max убрана и заменена поиск максимума на деке.
Линейный - это когда в худшем случае количество любых смещений при переборе элементов списка не превышает количества элементов этого списка.
Не совсем. Если требуется k*n смещений где k - константа - это всё равно линейный алгоритм.
Т.е. если мне надо всего 2 прохода (или 3, как здесь, но можно свести к 2) по массиву не зависимо от его длины, т.е. всегда 2. То алгоритм остается линейным.
Я не утверждаю ничего, но вроде, здесь никак она не может быть линейной.
Можно посчитать кодом, например, сколько раз делается смещений по потоку входных данных при полном их итерировании за всё время исполнения.
Если требуется k*n смещений где k - константа - это всё равно линейный алгоритм.
это k-кратный, кмк...
Т.е. если мне надо всего 2 прохода (или 3, как здесь, но можно свести к 2) по массиву не зависимо от его длины, т.е. всегда 2. То алгоритм остается линейным.
ещё же есть итерирование на каждом шаге именно внутри тела цикла нескольких элементов в зависимости от входного параметра:
разность индексов элементов идущих подряд была не менее K.
ещё же есть итерирование на каждом шаге именно внутри тела цикла нескольких элементов в зависимости от входного параметра:
Там работы с деком и если присмотреться то станет понятно, что каждый элемент последовательности в худшем случае будет помещён в дек не более одного раза и не более одного раза покинет дэк.
Соотвественно это все равно O(n)
xmoonlight, очевдино с момента когда график функции перестает быть прямой линией.
Даже 100500*n+800000000 - это уравнение прямой, а значит и сложность линейная
Александр Маджугин, да, верно.
Я обычно стараюсь, чтобы элемент, по-возможности, итерировался не более одного единственного раза, вот и подзабыл про y=kx+b..
Александр Маджугин, кстати, тут вот тоже про сложность этого алгоритма обсуждают и говорят, что в худшем случае - квадратичная она... (в коментах к ответу-лидеру).
В общем, я запутался тоже теперь)
xmoonlight, там обсуждают четный поиск минимум в скользящем окне.
В видео Елена говорит как раз что это действительно сложно O(n²) и описывает читерский вариант со стэком.
Александр Маджугин, мой вариант хуже или он не совсем понятен? Я не тестил ещё, но думаю он минимум не хуже того, который на данный момент отмечен решением.
PS: В целом, я склонен искать исключительно наилучшее решение.
Там работы с деком и если присмотреться то станет понятно, что каждый элемент последовательности в худшем случае будет помещён в дек не более одного раза и не более одного раза покинет дэк.
Соотвественно это все равно O(n)
нет. Тут ошибка!
Реальная сложность: O(2n) (как и сказала преподаватель из ролика с ютуба).
и ещё:
он не линеен, насколько я понимаю.
Как вы правильно заметили у него сложность (log n)
точнее, сложность O(n log n).
Сложность - обратно-нелинейная: чем меньше элементов, тем нужно всё меньшее и меньшее количество шагов. Чем больше - нужно больше шагов, но всегда меньше их двойного количества, т.е. меньше, чем 2n.
Итог: сложность O(2n) всегда будет больше сложности O(n log n). Можно убедиться просто посчитав с любым n два выражения. Поэтому, мой алгоритм работает быстрее при любой длине деки и с любым количеством элементов.
