Максимальная сумма непоследовательных элементов (с k элементами из любого места)

Question

Измененная версия вопроса "При наличии массива натуральных чисел, какой самый эффективный алгоритм для поиска непоследовательных элементов из этого массива, которые при сложении вместе дают максимальную сумму?" На стандартную версию ответили неплохо здесь .

Но что, если вы также можете выбрать указанное количество элементов из в любом месте в списке, независимо от того, последовательные они или нет? Как бы вы нашли максимальную сумму в этом случае?

Чтобы прояснить пример, скажем, вы строите дома. У вас есть n участков на выбор. С каждым лотом связана финансовая стоимость, X [i], которую вы получите, если построите там дом. Но из-за законов о зонировании вы не можете строить на последовательных лотах (поэтому, если вы строите на лотах № 5, вы не можете строить на № 4 или № 6). Вы хотите строить дома таким образом, чтобы максимизировать стоимость. Так что, если H [] - это список домов, которые вы должны построить, проблема будет H[i] = max ((H(i-1), H(i-2) + X[i])).

Но что теперь, если у вас есть дополнительные разрешения на k-зонирование (где вам дается k), которые позволяют вам строить где угодно, в дополнение к фиксированным лотам?

Answer 1

это можно решить с помощью простого алгоритма динамического программирования:

1. создать список кортежей (например, tuples);этот список содержит два объекта: общую стоимость построенных домов и список выбранных участков жилья (например, lots)
2. , который инициализирует список одним элементом со значением 0 и пустым списком участков * 1008.*
3. перебрать все возможные участки жилья.для каждого лота L:
4. цикл по списку: для каждого кортежа T в списке:
5. , если дом можно добавить в список участков жилья (т. е. естьменьше k лотов в списке, и добавление L не нарушит непоследовательное правило), создайте еще один элемент в списке, суммируйте значение T со значением построения на этом лоте (вы назвалиэто X[i]) и добавьте L в список lots в T.
6. .лучший выбор для жилищных участков хранится в том, что tuple 'lots

не уверен насчет сложности этого (n ^ 2 * k? - не могу думать прямо сейчас)но в целом это не так уж и плохо.

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

Answer 2

d[i][j] - динамический, сколько мы можем взять, если первый неиспользованный дом - i, и мы уже использовали j бонусы.

d[0][0] = 0;  
d[i][j] = max(d[i-1][j], d[i-2][j] + x[i], d[i-1][j-1] + x[i]);

Answer 3

Сначала выберите k лучших элементов, затем решите проблему «лучших непоследовательных целых чисел» в экземпляре без ранее выбранных элементов.