algorithm
Динамическое программирование
Поиск…
Вступление
Динамическое программирование является широко используемой концепцией и часто используется для оптимизации. Это относится к упрощению сложной проблемы, разбивая ее на более простые подзадачи рекурсивным образом, как правило, подход Bottom up. Существует два ключевых атрибута, которые должны иметь проблемы для динамического программирования: «Оптимальная субструктура» и «Перекрывающиеся подзадачи». Для достижения своей оптимизации в программе Dynamics используется концепция «Запоминание»
замечания
Динамическое программирование - это усовершенствование Brute Force, см. Этот пример, чтобы понять, как можно получить решение динамического программирования от Brute Force.
Решение Dynamic Programming Solution имеет два основных требования:
Проблемы с перекрытием
Оптимальная основа
Перекрывающиеся подзадачи означают, что результаты меньших версий проблемы повторно используются несколько раз, чтобы прийти к решению исходной проблемы
Оптимальная подструктура означает, что существует метод вычисления проблемы из ее подзадач.
Решение динамического программирования имеет 2 основных компонента: состояние и переход
Государство ссылается на подзадачу исходной проблемы.
Переход - это метод решения проблемы на основе ее подзадач
Время, затраченное на решение динамического программирования, можно рассчитать как число No. of States * Transition Time . Таким образом, если решение имеет N^2 состояния, а переход - O(N) , то решение займет примерно O(N^3) раз.
Проблема с рюкзаком
0-1 Рюкзак
Проблема с рюкзаком представляет собой проблему, когда задан набор элементов, каждый с весом, значением и ровно 1 копией , определяет, какие элементы (ы) включать в коллекцию, чтобы общий вес был меньше или равен заданному предел и общее значение как можно больше.
Пример C ++:
Реализация :
int knapsack(vector<int> &value, vector<int> &weight, int N, int C){
int dp[C+1];
for (int i = 1; i <= C; ++i){
dp[i] = -100000000;
}
dp[0] = 0;
for (int i = 0; i < N; ++i){
for (int j = C; j >= weight[i]; --j){
dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
}
}
return dp[C];
}
Тест :
3 5
5 2
2 1
3 2
Выход :
3
Это означает, что максимальное значение может быть достигнуто 3, что достигается выбором (2,1) и (3,2).
Неограниченный рюкзак
Проблема с неограниченным рюкзаком представляет собой проблему, которая задает набор элементов, каждый с весом, значением и бесконечными копиями , определяет количество каждого элемента, который должен быть включен в коллекцию, чтобы общий вес был меньше или равен заданному пределу и общее значение максимально возможно.
Python (2.7.11) Пример:
Реализация :
def unbounded_knapsack(w, v, c): # weight, value and capactiy
m = [0]
for r in range(1, c+1):
val = m[r-1]
for i, wi in enumerate(w):
if wi > r:
continue
val = max(val, v[i] + m[r-wi])
m.append(val)
return m[c] # return the maximum value can be achieved
Сложностью этой реализации является O(nC) , где n - количество элементов.
Тест :
w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]
print unbounded_knapsack(w, v, 13)
Выход :
20
Это означает, что максимальное значение может быть достигнуто равным 20, что достигается выбором (5, 8), (5, 8) и (3, 4).
Алгоритм взвешенного планирования работы
Алгоритм взвешенного планирования работы также можно обозначить как алгоритм выбора взвешенной активности.
Проблема в том, что с заданными заданиями с указанием времени начала и окончания времени и прибыль, которую вы делаете, когда вы заканчиваете работу, какова максимальная прибыль, которую вы можете сделать, если нет двух заданий, может выполняться параллельно?
Это выглядит как «Выбор действия», используя «Жадный алгоритм», но есть еще один поворот. То есть вместо максимизации количества завершенных заданий мы сосредоточимся на получении максимальной прибыли. Количество выполненных заданий здесь не имеет значения.
Давайте посмотрим на пример:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | A | B | C | D | E | F |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (2,5) | (6,7) | (7,9) | (1,3) | (5,8) | (4,6) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 6 | 4 | 2 | 5 | 11 | 5 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Работы обозначаются именем, временем начала и окончания и прибылью. После нескольких итераций мы можем узнать, выполняем ли мы Job-A и Job-E максимальную прибыль 17. Теперь, как найти это, используя алгоритм?
Первое, что мы делаем, - сортировать задания по времени окончания в неубывающем порядке. Почему мы это делаем? Это потому, что, если мы выберем задание, которое занимает меньше времени, то мы оставляем самое большое количество времени для выбора других заданий. У нас есть:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
У нас будет дополнительный временный массив Acc_Prof размером n (здесь n обозначает общее количество заданий). Это будет содержать максимальную накопленную прибыль от выполнения заданий. Не понял? Подождите и смотрите. Мы будем инициализировать значения массива с прибылью каждого задания. Это означает, что Acc_Prof [i] сначала получит прибыль от выполнения i-й работы.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Теперь давайте обозначим позицию 2 с i , а положение 1 обозначим через j . Наша стратегия будет состоять в повторении j от 1 до i-1, и после каждой итерации мы увеличим i на 1, пока i не станет n + 1 .
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Мы проверяем, перекрываются ли задания [i] и Job [j] , то есть, если время окончания работы [j] больше, чем время запуска Job [i] , то эти два задания не могут быть выполнены вместе. Однако, если они не перекрываются, мы проверим, есть ли Acc_Prof [j] + Profit [i]> Acc_Prof [i] . Если это так, мы обновим Acc_Prof [i] = Acc_Prof [j] + Profit [i] . То есть:
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
Здесь Acc_Prof [j] + Profit [i] представляет собой накопленную прибыль от выполнения этих двух заданий. Давайте проверим это для нашего примера:
Здесь Job [j] перекрывается с Job [i] . Таким образом, это невозможно сделать вместе. Так как наш j равен i-1 , мы увеличиваем значение i до i + 1 , равное 3 . И сделаем j = 1 .
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Теперь Job [j] и Job [i] не перекрываются. Общая сумма прибыли, которую мы можем сделать, выбрав эти два задания: Acc_Prof [j] + Profit [i] = 5 + 5 = 10, что больше, чем Acc_Prof [i] . Поэтому мы обновляем Acc_Prof [i] = 10 . Мы также увеличиваем j на 1. Получаем,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Здесь Job [j] перекрывается с Job [i], а j также равно i-1 . Поэтому мы увеличиваем i на 1 и делаем j = 1 . Мы получаем,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Теперь Job [j] и Job [i] не перекрываются, мы получаем накопленную прибыль 5 + 4 = 9 , которая больше Acc_Prof [i] . Мы обновляем Acc_Prof [i] = 9 и увеличиваем j на 1.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 9 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Опять Job [j] и Job [i] не перекрываются. Накопленная прибыль равна: 6 + 4 = 10 , что больше, чем Acc_Prof [i] . Мы снова обновляем Acc_Prof [i] = 10 . Мы увеличиваем j на 1. Получаем:
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 10 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Если мы продолжим этот процесс, после повторения всей таблицы с помощью i наша таблица будет выглядеть следующим образом:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 14 | 17 | 8 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Несколько шагов были пропущены, чтобы сделать документ короче.
Если мы итерации через массив Acc_Prof , мы можем узнать, что максимальная прибыль равна 17 ! Псевдокод:
Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
for j -> 1 to i-1
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
endfor
endfor
maxProfit = 0
for i -> 1 to n
if maxProfit < Acc_Prof[i]
maxProfit = Acc_Prof[i]
return maxProfit
Сложность заполнения массива Acc_Prof равна O (n 2 ). Обход массива принимает O (n) . Таким образом, общая сложность этого алгоритма равна O (n 2 ).
Теперь, если мы хотим узнать, какие задания были выполнены для получения максимальной прибыли, нам нужно пройти массив в обратном порядке, и если Acc_Prof соответствует maxProfit , мы будем вызывать имя задания в стеке и вычитать прибыль эта работа от maxProfit . Мы будем делать это до нашего maxProfit> 0 или мы достигнем начальной точки массива Acc_Prof . Псевдокод будет выглядеть так:
Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
if maxProfit is equal to Acc_Prof[i]
S.push(Job[i].name
maxProfit = maxProfit - Job[i].profit
endif
endfor
Сложность этой процедуры: O (n) .
Помните, что если есть несколько графиков работы, которые могут дать нам максимальную прибыль, мы можем найти только один график работы с помощью этой процедуры.
Изменить расстояние
Оператор проблемы похож, если нам даны две строки str1 и str2, то сколько минимального количества операций может быть выполнено на str1, которое оно преобразует в str2.
Реализация на Java
public class EditDistance {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "march";
String str2 = "cart";
EditDistance ed = new EditDistance();
System.out.println(ed.getMinConversions(str1, str2));
}
public int getMinConversions(String str1, String str2){
int dp[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0)
dp[i][j] = j;
else if(j==0)
dp[i][j] = i;
else if(str1.charAt(i-1) == str2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
}
}
}
return dp[str1.length()][str2.length()];
}
}
Выход
3
Самая длинная общая подпоследовательность
Если нам заданы две строки, мы должны найти самую длинную общую подпоследовательность, присутствующую в обеих из них.
пример
LCS для входных последовательностей «ABCDGH» и «AEDFHR» - это «ADH» длины 3.
LCS для входных последовательностей «AGGTAB» и «GXTXAYB» - это «GTAB» длины 4.
Реализация на Java
public class LCS {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "AGGTAB";
String str2 = "GXTXAYB";
LCS obj = new LCS();
System.out.println(obj.lcs(str1, str2, str1.length(), str2.length()));
System.out.println(obj.lcs2(str1, str2));
}
//Recursive function
public int lcs(String str1, String str2, int m, int n){
if(m==0 || n==0)
return 0;
if(str1.charAt(m-1) == str2.charAt(n-1))
return 1 + lcs(str1, str2, m-1, n-1);
else
return Math.max(lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1));
}
//Iterative function
public int lcs2(String str1, String str2){
int lcs[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0 || j== 0){
lcs[i][j] = 0;
}
else if(str1.charAt(i-1) == str2.charAt(j-1)){
lcs[i][j] = 1 + lcs[i-1][j-1];
}else{
lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
}
}
}
return lcs[str1.length()][str2.length()];
}
}
Выход
4
Число Фибоначчи
Нижний подход для печати n-го числа Фибоначчи с использованием динамического программирования.
Рекурсивное дерево
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
Перекрывающиеся суб-проблемы
Здесь fib (0), fib (1) и fib (3) являются перекрывающимися подзадачами. Fib (0) повторяется 3 раза, fib (1) повторяется 5 раз, а fib (3) повторяется 2 раз.
Реализация
public int fib(int n){
int f[] = new int[n+1];
f[0]=0;f[1]=1;
for(int i=2;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
Сложность времени
На)
Самая длинная общая подстрока
Учитывая 2 строки str1 и str2, мы должны найти длину самой длинной общей подстроки между ними.
Примеры
Вход: X = "abcdxyz", y = "xyzabcd" Выход: 4
Самая длинная общая подстрока - «abcd» и имеет длину 4.
Вход: X = "zxabcdezy", y = "yzabcdezx" Выход: 6
Самая длинная общая подстрока - «abcdez» и имеет длину 6.
Реализация на Java
public int getLongestCommonSubstring(String str1,String str2){
int arr[][] = new int[str2.length()+1][str1.length()+1];
int max = Integer.MIN_VALUE;
for(int i=1;i<=str2.length();i++){
for(int j=1;j<=str1.length();j++){
if(str1.charAt(j-1) == str2.charAt(i-1)){
arr[i][j] = arr[i-1][j-1]+1;
if(arr[i][j]>max)
max = arr[i][j];
}
else
arr[i][j] = 0;
}
}
return max;
}
Сложность времени
О (т * п)