Articles of динамического программирования

Сокращение временной сложности Knapsack 0 ~ 1 при использовании алгоритма DP

Я использую алгоритм DP, т. Е. Сохраняю значения подзадачи в 2D-массиве, где одна ось означает n элементов и других значений w от 0 до W где W – максимальное значение емкость рюкзака. Поэтому значение T[n-1][W] является оптимальным для меня вычислить. Я читал в других источниках, что временная сложность этого алгоритма O(nW) . Мой quesiton был […]

Алгоритм для нахождения максимальной суммы элементов в массиве, так что не более k элементов смежны

Я столкнулся с этим вопросом. Для массива, содержащего только положительные значения, вы хотите максимизировать сумму выбранных элементов при ограничении, что ни одна группа из более чем выбранных элементов не смежна. Например, если вход 1 2 3 1 7 9 (n = 6 и k = 2). Выходной сигнал будет равен 21, который исходит от выбора […]

Найти подмножество размера k таким образом, чтобы минимальное расстояние между значениями было максимальным

Предположим, что у меня есть массив, содержащий n целых чисел. Как найти подмножество размера k , так что minimum расстояние между всеми парами целых чисел в подмножестве maximized , я имею в виду, что они находятся на самом дальнем расстоянии. пример: array a[]={1,2,6,7,10} и k=3 , subset = {1,6,10} , минимальное расстояние 4 между 10 […]

Bytelandian Gold Coin, Динамическое программирование, объяснение?

Это немного незрело, но я должен спросить, Проблема, о которой упоминается здесь, – проблема, о которой упоминается здесь, – http://www.codechef.com/problems/COINS/ , считается типичной проблемой DP, хотя я читал основы DP и рекурсии, но мне трудно понять ее решение, # include # include long unsigned int costArray[30][19]; unsigned int amount; unsigned int currentValue(short int factor2,short int […]

Самая длинная общая подпоследовательность для нескольких последовательностей

Я провел кучу исследований, чтобы найти самый длинный для M = 2 последовательностей, но я пытаюсь выяснить, как это сделать для M ≥ 2 последовательностей Мне даются последовательности N и M: M, с N уникальными элементами. N – множество {1 – N}. Я думал о подходе к динамическому программированию, но я все еще смущен тем, […]