Как максимизировать сумму элементов выбираемых из списка?

Дан список натуральных положительных.
Из списка можно выбрать некоторое количество элементов, таким образом, чтобы разность индексов элементов идущих подряд была не менее 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

Какие есть идеи? Время поиска комбинаций важно - списки длинные.
  • Вопрос задан
  • 872 просмотра
Решения вопроса 1
@Aleshonne
Научные вычисления
В общем, примерный план решения такой:
Начинаем смотреть элементы с конца списка. Последние k элементов заносятся в кэш как есть, от них никуда не деться. Далее для каждого элемента с номером i нужно просмотреть, как он сочетается с элементами i + k .. i + 2k. Дальше смотреть смысла нет, так как это только ухудшит ситуацию. И так идём до первого элемента. Потом выбираем лучший из элементов с номерами 1 .. k. Вроде как получается линейный относительно размера списка код (не более k(n + 1) операций).
Код реализации:
https://ideone.com/ZU8Mrr
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
@dmshar
А есть-ли ограничения на количество элементов в списке? Если есть - я бы сделал так: Построил бы все комбинации из допустимого количества элементов, просчитав при этом их суммы. Потом бы отсортировал эти объекты по спаданию суммы, а потом начиная с наибольшей суммы проверял-бы удовлетворяется-ли условие по К. (это очень просто). Как только условие удовлетворено - максимально возможная сумма найдена.

Но если вдруг указанного ограничения нет - то увы, возвращаемся опять к NP-сложной задаче.
Ответ написан
@koperagen
Нужно создать дополнительный список 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])
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Это стандартная задача на динамическое программирование. Например заведите 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[].
Ответ написан
Комментировать
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
К примеру дан список:
7, 18, 6, 10, 12, 128
K>=3
1.Сначала сплитим поток с наивысшей частотой (K=>min) на несколько групп в рамках одного минимального периода (K) и ищем наибольшую сумму в каждой такой группе:
7, 10
18, 12
6, 128 (наибольшая сумма)

2.Затем, раздвигаем диапазон в обратную сторону:
18, 128 (наибольшая сумма)
7, 128

3.Повторяем всё тоже самое с найденного места опять с минимальным K, постепенно увеличивая его до размера найденного расстояния в предыдущем шаге.
И так до тех пор, пока не закончится весь входной поток значений.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы