Поиск максимальной подпоследовательности ниже или равный определенному значению

Question

Я изучаю динамическое программирование, и у меня возникли проблемы с пониманием более сложных проблем. Когда возникает проблема, меня научили находить рекурсивный алгоритм, memoize рекурсивный алгоритм, а затем создать итеративную снизу вверх версию. На каждом шагу у меня проблема. В терминах рекурсивного алгоритма я пишу разные способы выполнения рекурсивных алгоритмов, но только один из них часто оптимален для использования в динамическом программировании, и я не могу отличить, какие аспекты рекурсивного алгоритма облегчают мемонирование. Что касается memoization, я не понимаю, какие значения использовать для индексов. Для преобразования в восходящую версию я не могу определить, какой заказ заполнить массив/двойной массив.

Это то, что я понимаю: - это должно быть возможно разделить основную задачу на подзадачи

В терминах задачи упоминалось, я придумал рекурсивный алгоритм, который имеет эти важные строки кода :

int optionOne = values[i] + find(values, i+1, limit - values[i]); 
int optionTwo = find(values, i+1, limit); 

Если я неясен или это не правильный сайт qa, дайте мне знать.

Редактировать:

Пример: Учитывая массив х: [4,5,6,9,11] и максимальное значение м: 20

Максимальная подпоследовательность х под или равна т будет [4 , 5,11] как 4 + 5 + 11 = 20

Answer 1

Я думаю, что эта проблема NP-hard, что означает, что если P = NP не существует алгоритма полиномиального времени для решения проблемы.

Для решения этой проблемы существует простое сокращение от проблемы с подмножеством. В подмножестве-сумме вам предоставляется набор из n чисел и номер цели k и вы хотите определить, есть ли подмножество этих чисел, которое составляет ровно k. Вы можете решить подмножество суммы с решателем для своей проблемы следующим образом: создать массив чисел в наборе и найти самую большую подпоследовательность, сумма которой меньше или равна k. Если это составляет ровно k, набор имеет подмножество, которое добавляет до k. В противном случае это не так.

Это сокращение занимает многочленное время, поэтому, поскольку сумма подмножеств NP-hard, ваша проблема также NP-hard. Поэтому я сомневаюсь, что существует алгоритм с полиномиальным временем.

Сказанное - существует алгоритм псевдополиномиального времени для подмножества-суммы, который равен described on Wikipedia. Этот алгоритм использует DP в двух переменных и не является строго полиномиальным временем, но он, вероятно, будет работать в вашем случае.

Надеюсь, это поможет!