algorithm
Programación dinámica
Buscar..
Introducción
La programación dinámica es un concepto ampliamente utilizado y se utiliza a menudo para la optimización. Se refiere a simplificar un problema complicado dividiéndolo en subproblemas más simples de manera recursiva, por lo general con un enfoque ascendente. Hay dos atributos clave que debe tener un problema para que la programación dinámica sea aplicable "Subestructura óptima" y "Subproblemas superpuestos". Para lograr su optimización, la programación de Dinámica utiliza un concepto llamado Memorización.
Observaciones
La programación dinámica es una mejora de Brute Force; vea este ejemplo para comprender cómo se puede obtener una solución de programación dinámica de Brute Force.
Una solución de programación dinámica tiene 2 requisitos principales:
Problemas superpuestos
Subestructura óptima
La superposición de subproblemas significa que los resultados de versiones más pequeñas del problema se reutilizan varias veces para llegar a la solución del problema original.
Subestructura óptima significa que existe un método para calcular un problema a partir de sus subproblemas.
Una solución de programación dinámica tiene 2 componentes principales, el estado y la transición
El Estado se refiere a un subproblema del problema original.
La transición es el método para resolver un problema basado en sus subproblemas
El tiempo que tarda una solución de programación dinámica se puede calcular como el No. of States * Transition Time . Por lo tanto, si una solución tiene N^2 estados y la transición es O(N) , entonces la solución tomaría aproximadamente O(N^3) tiempo.
Problema de mochila
0-1 Mochila
El problema de la mochila es un problema cuando se le asigna un conjunto de artículos, cada uno con un peso, un valor y exactamente 1 copia , determina qué artículos deben incluirse en una colección para que el peso total sea menor o igual que un determinado Límite y el valor total es lo más grande posible.
Ejemplo de C ++:
Implementación :
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];
}
Prueba :
3 5
5 2
2 1
3 2
Salida :
3
Eso significa que el valor máximo que se puede alcanzar es 3, que se logra al elegir (2,1) y (3,2).
Mochila sin límites
El problema de la mochila sin límites es un problema que, dado un conjunto de elementos, cada uno con un peso, un valor y copias infinitas , determina el número de cada artículo que se incluirá en una colección de modo que el peso total sea menor o igual a un límite dado y el valor total es lo más grande posible.
Python (2.7.11) Ejemplo:
Implementación :
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
La complejidad de esa implementación es O(nC) , que n es el número de elementos.
Prueba :
w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]
print unbounded_knapsack(w, v, 13)
Salida :
20
Eso significa que el valor máximo que se puede alcanzar es 20, que se logra al elegir (5, 8), (5, 8) y (3, 4).
Algoritmo de programación de trabajo ponderado
El algoritmo ponderado de programación de trabajos también se puede denotar como algoritmo ponderado de selección de actividades.
El problema es que, dados ciertos trabajos con su hora de inicio y finalización, y el beneficio que obtiene cuando termina el trabajo, ¿cuál es el beneficio máximo que puede obtener dado que no se pueden ejecutar dos trabajos en paralelo?
Este se parece a la Selección de Actividad usando el Algoritmo Greedy, pero hay un giro adicional. Es decir, en lugar de maximizar el número de trabajos finalizados, nos centramos en obtener el máximo beneficio. La cantidad de trabajos realizados no importa aquí.
Veamos un ejemplo:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Los trabajos se indican con un nombre, su hora de inicio y finalización y las ganancias. Después de algunas iteraciones, podemos averiguar si realizamos Job-A y Job-E , podemos obtener el máximo beneficio de 17. ¿Cómo descubrir esto utilizando un algoritmo?
Lo primero que hacemos es clasificar los trabajos por su tiempo de finalización en orden no decreciente. ¿Por qué hacemos esto? Es porque si seleccionamos un trabajo que demora menos tiempo en terminar, dejamos la mayor cantidad de tiempo para elegir otros trabajos. Tenemos:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Tendremos una matriz temporal adicional Acc_Prof de tamaño n (Aquí, n indica el número total de trabajos). Esto contendrá el beneficio acumulado máximo de realizar los trabajos. ¿No lo entiendes? Espera y mira. Inicializaremos los valores de la matriz con el beneficio de cada trabajo. Eso significa que Acc_Prof [i] al principio tendrá el beneficio de realizar el trabajo i-th .
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ahora denotemos la posición 2 con i , y la posición 1 se denotará con j . Nuestra estrategia será iterar j de 1 a i-1 y después de cada iteración, incrementaremos i en 1, hasta que i se convierta en 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Verificamos si la Tarea [i] y la Tarea [j] se superponen, es decir, si la hora de finalización de la Tarea [j] es mayor que la hora de inicio de la Tarea [i] , entonces estas dos tareas no se pueden hacer juntas. Sin embargo, si no se superponen, verificaremos si Acc_Prof [j] + Profit [i]> Acc_Prof [i] . Si este es el caso, actualizaremos Acc_Prof [i] = Acc_Prof [j] + Profit [i] . Es decir:
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
Aquí, Acc_Prof [j] + Profit [i] representa el beneficio acumulado de hacer estos dos trabajos juntos. Vamos a comprobarlo para nuestro ejemplo:
Aquí el trabajo [j] se superpone con el trabajo [i] . Así que estos no se pueden hacer juntos. Como nuestra j es igual a i-1 , incrementamos el valor de i a i + 1 que es 3 . Y hacemos 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ahora Job [j] y Job [i] no se superponen. La cantidad total de ganancias que podemos obtener al elegir estos dos trabajos es: Acc_Prof [j] + Profit [i] = 5 + 5 = 10, que es mayor que Acc_Prof [i] . Así que actualizamos Acc_Prof [i] = 10 . También incrementamos j en 1. Obtenemos,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Aquí, la tarea [j] se superpone con la tarea [i] y j también es igual a i-1 . Entonces incrementamos i por 1, y hacemos j = 1 . Obtenemos,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ahora, Job [j] y Job [i] no se superponen, obtenemos el beneficio acumulado 5 + 4 = 9 , que es mayor que Acc_Prof [i] . Actualizamos Acc_Prof [i] = 9 e incrementamos j en 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
De nuevo, Job [j] y Job [i] no se superponen. El beneficio acumulado es: 6 + 4 = 10 , que es mayor que Acc_Prof [i] . Nuevamente actualizamos Acc_Prof [i] = 10 . Incrementamos j en 1. Obtenemos:
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Si continuamos este proceso, después de recorrer toda la tabla usando i , nuestra tabla finalmente se verá así:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Se han saltado algunos pasos para acortar el documento.
¡Si iteramos a través de la matriz Acc_Prof , podemos encontrar la ganancia máxima de 17 ! El pseudocódigo:
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
La complejidad de llenar la matriz Acc_Prof es O (n 2 ). El recorrido transversal de la matriz toma O (n) . Entonces, la complejidad total de este algoritmo es O (n 2 ).
Ahora, si queremos averiguar qué trabajos se realizaron para obtener el máximo beneficio, debemos atravesar la matriz en orden inverso y si Acc_Prof coincide con maxProfit , empujaremos el nombre del trabajo en una pila y restaremos Ganancia de ese trabajo de maxProfit . Haremos esto hasta que nuestro maxProfit> 0 o alcancemos el punto de inicio de la matriz Acc_Prof . El pseudocódigo se verá así:
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
La complejidad de este procedimiento es: O (n) .
Una cosa para recordar, si hay varios horarios de trabajo que pueden darnos el máximo beneficio, solo podemos encontrar un programa de trabajo a través de este procedimiento.
Editar distancia
La declaración del problema es como si nos dieran dos cadenas str1 y str2, entonces, ¿cuántas operaciones mínimas se pueden realizar en el str1 que se convierte en str2?
Implementación en 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()];
}
}
Salida
3
La subsecuencia común más larga
Si nos dan con las dos cadenas, tenemos que encontrar la subsecuencia común más larga presente en ambas.
Ejemplo
LCS para secuencias de entrada “ABCDGH” y “AEDFHR” es “ADH” de longitud 3.
LCS para secuencias de entrada "AGGTAB" y "GXTXAYB" es "GTAB" de longitud 4.
Implementación en 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()];
}
}
Salida
4
Número de Fibonacci
Enfoque de abajo hacia arriba para imprimir el número n de Fibonacci utilizando la programación dinámica.
Árbol recursivo
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)
Sub-problemas superpuestos
En este caso, fib (0), fib (1) y fib (3) son los subproblemas superpuestos. Fib (0) se repite 3 veces, fib (1) se repite 5 veces y fib (3) se repite 2 veces.
Implementación
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];
}
Complejidad del tiempo
En)
La subcadena común más larga
Teniendo en cuenta 2 cadenas str1 y str2, tenemos que encontrar la longitud de la subcadena común más larga entre ellas.
Ejemplos
Entrada: X = "abcdxyz", y = "xyzabcd" Salida: 4
La subcadena común más larga es "abcd" y tiene una longitud de 4.
Entrada: X = "zxabcdezy", y = "yzabcdezx" Salida: 6
La subcadena común más larga es "abcdez" y tiene una longitud de 6.
Implementación en 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;
}
Complejidad del tiempo
O (m * n)