Programaci贸n din谩mica en Java

    Introducci贸n

    La programaci贸n din谩mica se utiliza normalmente para optimizar algoritmos recursivos, ya que tienden a escalar exponencialmente. La idea principal es dividir los problemas complejos (con muchas llamadas recursivas) en subproblemas m谩s peque帽os y luego guardarlos en la memoria para que no tengamos que volver a calcularlos cada vez que los usemos.

    Para comprender los conceptos de programaci贸n din谩mica, debemos familiarizarnos con algunos temas:

    • 驴Qu茅 es la programaci贸n din谩mica?
    • Algoritmo de corte de varilla
    • El problema simplificado de la mochila
    • El problema de la mochila tradicional
    • Distancia de Levenshtein
    • LCS – Subsecuencia com煤n m谩s larga
    • Otros problemas que utilizan la programaci贸n din谩mica
    • Conclusi贸n

    驴Qu茅 es la programaci贸n din谩mica?

    La programaci贸n din谩mica es un principio de programaci贸n en el que un problema muy complejo se puede resolver dividi茅ndolo en subproblemas m谩s peque帽os. Este principio es muy similar a la recursividad, pero con una diferencia clave, cada subproblema distinto debe resolverse solo una vez.

    Para comprender lo que esto significa, primero tenemos que comprender el problema de resolver las relaciones de recurrencia. Cada problema complejo puede dividirse en subproblemas muy similares, esto significa que podemos construir una relaci贸n de recurrencia entre ellos.

    Echemos un vistazo a un ejemplo con el que todos estamos familiarizados, 隆la secuencia de Fibonacci ! La secuencia de Fibonacci se define con la siguiente relaci贸n de recurrencia:

    $$
    fibonacci (n) = fibonacci (n-1) + fibonacci (n-2)
    $$

    Nota: Una relaci贸n de recurrencia es una ecuaci贸n que define de forma recursiva una secuencia en la que el siguiente t茅rmino es una funci贸n de los t茅rminos anteriores. La secuencia de Fibonacci es un gran ejemplo de esto.

    Entonces, si queremos encontrar el n-thn煤mero en la secuencia de Fibonacci, tenemos que conocer los dos n煤meros que preceden al n-then la secuencia.

    Sin embargo, cada vez que queremos calcular un elemento diferente de la secuencia de Fibonacci, tenemos ciertas llamadas duplicadas en nuestras llamadas recursivas, como se puede ver en la siguiente imagen, donde calculamos Fibonacci (5):

    Por ejemplo, si queremos calcular F (5), obviamente necesitamos calcular F (4) y F (3) como requisito previo. Sin embargo, para calcular F (4), necesitamos calcular F (3) y F (2), lo que a su vez requiere que calculemos F (2) y F (1) para obtener F (3) – y as铆 en.

    Esto conduce a muchos c谩lculos repetidos, que son esencialmente redundantes y ralentizan significativamente el algoritmo. Para resolver este problema, nos presentamos a la programaci贸n din谩mica .

    En este enfoque, modelamos una soluci贸n como si la resolvi茅ramos de forma recursiva, pero la resolvemos desde cero, memorizando las soluciones a los subproblemas (pasos) que damos para llegar a la cima.

    Por lo tanto, para la secuencia de Fibonacci, primero resolvemos y memorizamos F (1) y F (2), luego calculamos F (3) usando los dos pasos memorizados, y as铆 sucesivamente. Esto significa que el c谩lculo de cada elemento individual de la secuencia es O (1), porque ya conocemos los dos primeros.

    A la hora de resolver un problema mediante programaci贸n din谩mica, tenemos que seguir tres pasos:

    • Determinar la relaci贸n de recurrencia que aplica a dicho problema.
    • Inicializar los valores iniciales de la memoria / matriz / matriz
    • Aseg煤rese de que cuando hacemos una “llamada recursiva” (accedemos a la soluci贸n memorizada de un subproblema) siempre se resuelve de antemano.

    Siguiendo estas reglas, echemos un vistazo a algunos ejemplos de algoritmos que utilizan programaci贸n din谩mica.

    Algoritmo de corte de varilla

    Comencemos con algo simple:

    Dada una varilla de longitud ny una matriz que contiene precios de todas las piezas de tama帽o menor que n. Determine el valor m谩ximo que se puede obtener cortando la varilla y vendiendo las piezas.

    Soluci贸n ingenua

    Este problema est谩 pr谩cticamente hecho a medida para la programaci贸n din谩mica, pero como este es nuestro primer ejemplo real, veamos cu谩ntos incendios podemos iniciar dejando que se ejecute este c贸digo:

    public class naiveSolution {
        static int getValue(int[] values, int length) {
            if (length <= 0)
                return 0;
            int tmpMax = -1;
            for (int i = 0; i < length; i++) {
                tmpMax = Math.max(tmpMax, values[i] + getValue(values, length - i - 1));
            }
            return tmpMax;
        }
    
        public static void main(String[] args) {
            int[] values = new int[]{3, 7, 1, 3, 9};
            int rodLength = values.length;
    
            System.out.println("Max rod value: " + getValue(values, rodLength));
        }
    }
    

    Salida:

    Max rod value: 17
    

    Esta soluci贸n, aunque correcta, es muy ineficaz . Las llamadas recursivas no se memorizan, por lo que el c贸digo deficiente tiene que resolver el mismo subproblema cada vez que hay una 煤nica soluci贸n superpuesta.

    Enfoque din谩mico

    Utilizando el mismo principio b谩sico anterior, pero agregando memorizaci贸n y excluyendo llamadas recursivas, obtenemos la siguiente implementaci贸n:

    public class dpSolution {
        static int getValue(int[] values, int rodLength) {
            int[] subSolutions = new int[rodLength + 1];
    
            for (int i = 1; i <= rodLength; i++) {
                int tmpMax = -1;
                for (int j = 0; j < i; j++)
                    tmpMax = Math.max(tmpMax, values[j] + subSolutions[i - j - 1]);
                subSolutions[i] = tmpMax;
            }
            return subSolutions[rodLength];
        }
    
        public static void main(String[] args) {
            int[] values = new int[]{3, 7, 1, 3, 9};
            int rodLength = values.length;
    
            System.out.println("Max rod value: " + getValue(values, rodLength));
        }
    }
    

    Salida:

    Max rod value: 17
    

    Como podemos ver, las salidas resultantes son las mismas, solo que con diferente complejidad de tiempo / espacio.

    Eliminamos la necesidad de llamadas recursivas resolviendo los subproblemas desde cero, utilizando el hecho de que todos los subproblemas anteriores a un problema dado ya est谩n resueltos.

    Mejora del rendimiento

    Solo para dar una perspectiva de cu谩nto m谩s eficiente es el enfoque din谩mico, intentemos ejecutar el algoritmo con 30 valores.

    La soluci贸n Naive tard贸 ~ 5.2 s en ejecutarse, mientras que la soluci贸n din谩mica tard贸 ~ 0.000095 s en ejecutarse.

    Problema simplificado de la mochila

    El problema de la Mochila Simplificada es un problema de optimizaci贸n, para el que no existe una soluci贸n 煤nica. La pregunta para este problema ser铆a: “驴Existe una soluci贸n?”:

    Dado un conjunto de art铆culos, cada uno con un peso w1, w2… determine el n煤mero de cada art铆culo para poner en una mochila para que el peso total sea menor o igual a un l铆mite dado K.

    As铆 que demos un paso atr谩s y descubramos c贸mo representaremos las soluciones a este problema. Primero, almacenemos los pesos de todos los elementos en una matriz W.

    A continuaci贸n, digamos que hay nelementos y los enumeraremos con n煤meros de 1 to n, por lo que el peso del i-thelemento es W[i].

    Formaremos una matriz Mde (n+1)x (K+1)dimensiones. M[x][y]correspondiente a la soluci贸n del problema de la mochila, pero solo incluyendo los primeros xelementos del arreglo inicial, y con una capacidad m谩xima de y.

    Ejemplo

    Digamos que tenemos 3 elementos, siendo las ponderaciones w1=2kg, w2=3kgy w3=4kg.

    Utilizando el m茅todo anterior, podemos decir que M[1][2]es una soluci贸n v谩lida. Esto significa que estamos intentando llenar una mochila con una capacidad de 2 kg con solo el primer art铆culo de la matriz de pesos ( w1).

    Mientras M[3][5]que estamos tratando de llenar una mochila con una capacidad de 5 kg utilizando los primeros 3elementos de la matriz de peso ( w1,w2,w3). Esta no es una soluci贸n v谩lida, ya que la estamos sobreajustando.

    Inicializaci贸n de matriz

    Hay 2 cosas a tener en cuenta al completar la matriz:

    驴Existe una soluci贸n para el subproblema dado (M [x] [y] .existe) Y la soluci贸n dada incluye el 煤ltimo elemento agregado a la matriz (M [x] [y] .incluye).

    Por lo tanto, la inicializaci贸n de la matriz es bastante f谩cil, M[0][k].existssiempre false, si k > 0, porque no pusimos ning煤n art铆culo en una mochila con kcapacidad.

    Por otro lado, M[0][0].exists = trueporque la mochila debe estar vac铆a para empezar desde k = 0, y por lo tanto no podemos meter nada y esta es una soluci贸n v谩lida.

    Adem谩s, podemos decir eso M[k][0].exists = truepero tambi茅n M[k][0].includes = falsepara todos k.

    Nota : El hecho de que exista una soluci贸n para un determinado M[x][y], no significa necesariamente que esa combinaci贸n en particular sea la soluci贸n. En el caso de M[10][0], existe una soluci贸n, sin incluir ninguno de los 10 elementos. Por eso, M[10][0].exists = truepero M[10][0].includes = false.

    Principio de algoritmo

    A continuaci贸n, construyamos la relaci贸n de recurrencia para M[i][k]con el siguiente pseudoc贸digo:

    if (M[i-1][k].exists == True):
        M[i][k].exists = True
        M[i][k].includes = False
    elif (k-W[i]>=0):
        if(M[i-1][k-W[i]].exists == true):
            M[i][k].exists = True
            M[i][k].includes = True
    else:
        M[i][k].exists = False
    

    Entonces, la esencia de la soluci贸n es dividir el subproblema en dos casos:

    • Cuando existe una soluci贸n para los primeros i-1elementos, para la capacidadk
    • Cuando existe una soluci贸n para los primeros i-1elementos, pero para la capacidadk-W[i]

    El primer caso se explica por s铆 mismo, ya tenemos una soluci贸n al problema.

    El segundo caso se refiere a conocer la soluci贸n para los primeros i-1elementos, pero la capacidad est谩 con exactamente un i-thelemento antes de estar llena, lo que significa que solo podemos agregar un i-thelemento, 隆y tenemos una nueva soluci贸n!

    Implementaci贸n

    En esta implementaci贸n, para facilitar las cosas, crearemos la clase Elementpara almacenar elementos:

    public class Element {
        private boolean exists;
        private boolean includes;
    
        public Element(boolean exists, boolean includes) {
            this.exists = exists;
            this.includes = includes;
        }
    
        public Element(boolean exists) {
            this.exists = exists;
            this.includes = false;
        }
    
        public boolean isExists() {
            return exists;
        }
    
        public void setExists(boolean exists) {
            this.exists = exists;
        }
    
        public boolean isIncludes() {
            return includes;
        }
    
        public void setIncludes(boolean includes) {
            this.includes = includes;
        }
    }
    

    Ahora podemos sumergirnos en la clase principal:

    public class Knapsack {
        public static void main(String[] args) {
            Scanner scanner = new Scanner (System.in);
    
            System.out.println("Insert knapsack capacity:");
            int k = scanner.nextInt();
    
            System.out.println("Insert number of items:");
            int n = scanner.nextInt();
    
            System.out.println("Insert weights: ");
            int[] weights = new int[n + 1];
    
            for (int i = 1; i <= n; i++) {
                weights[i] = scanner.nextInt();
            }
    
            Element[][] elementMatrix = new Element[n + 1][k + 1];
    
            elementMatrix[0][0] = new Element(true);
    
            for (int i = 1; i <= k; i++) {
                elementMatrix[0][i] = new Element(false);
            }
    
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= k; j++) {
                    elementMatrix[i][j] = new Element(false);
                    if (elementMatrix[i - 1][j].isExists()) {
                        elementMatrix[i][j].setExists(true);
                        elementMatrix[i][j].setIncludes(false);
                    } else if (j >= weights[i]) {
                        if (elementMatrix[i - 1][j - weights[i]].isExists()) {
                            elementMatrix[i][j].setExists(true);
                            elementMatrix[i][j].setIncludes(true);
                        }
                    }
                }
            }
    
            System.out.println(elementMatrix[n][k].isExists());
        }
    }
    

    Lo 煤nico que queda es la reconstrucci贸n de la soluci贸n, en la clase anterior, sabemos que EXISTE una soluci贸n, sin embargo, no sabemos qu茅 es.

    Para la reconstrucci贸n usamos el siguiente c贸digo:

    List<Integer> solution = new ArrayList<>(n);
    
    if (elementMatrix[n][k].isExists()) {
        int i = n;
        int j = k;
        while (j > 0 && i > 0) {
            if (elementMatrix[i][j].isIncludes()) {
                solution.add(i);
                j = j - weights[i];
            }
            i = i - 1;
        }
    }
    
    System.out.println("The elements with the following indexes are in the solution:n" + (solution.toString()));
    

    Salida:

    Insert knapsack capacity:
    12
    Insert number of items:
    5
    Insert weights:
    9 7 4 10 3
    true
    The elements with the following indexes are in the solution:
    [5, 1]
    

    Una simple variaci贸n del problema de la mochila es llenar una mochila sin optimizaci贸n de valor, pero ahora con cantidades ilimitadas de cada art铆culo individual.

    Esta variaci贸n se puede resolver haciendo un simple ajuste a nuestro c贸digo existente:

    // Old code for simplified knapsack problem
    else if (j >= weights[i]) {
        if (elementMatrix[i - 1][j - weights[i]].isExists()) {
            elementMatrix[i][j].setExists(true);
            elementMatrix[i][j].setIncludes(true);
        }
    }
    
    // New code, note that we're searching for a solution in the same
    // row (i-th row), which means we're looking for a solution that
    // already has some number of i-th elements (including 0) in it's solution
    else if (j >= weights[i]) {
        if (elementMatrix[i][j - weights[i]].isExists()) {
            elementMatrix[i][j].setExists(true);
            elementMatrix[i][j].setIncludes(true);
        }
    }
    

    El problema de la mochila tradicional

    Utilizando las dos variaciones anteriores, echemos un vistazo al problema tradicional de la mochila y veamos en qu茅 se diferencia de la variaci贸n simplificada:

    Dado un conjunto de art铆culos, cada uno con un peso w1, w2… y un valor v1, v2… determinar el n煤mero de cada art铆culo para incluir en una colecci贸n de modo que el peso total sea menor o igual a un l铆mite dado ky el valor total es lo m谩s grande posible.

    En la versi贸n simplificada, todas las soluciones eran igualmente buenas. Sin embargo, ahora tenemos un criterio para encontrar una soluci贸n 贸ptima (tambi茅n conocida como el valor m谩s grande posible). Tenga en cuenta que esta vez tenemos un n煤mero infinito de cada elemento, por lo que los elementos pueden aparecer varias veces en una soluci贸n.

    En la implementaci贸n usaremos la clase anterior Element, con un campo privado agregado valuepara almacenar el mayor valor posible para un subproblema dado:

    public class Element {
        private boolean exists;
        private boolean includes;
        private int value;
        // appropriate constructors, getters and setters
    }
    

    La implementaci贸n es muy similar, con la 煤nica diferencia de que ahora tenemos que elegir la soluci贸n 贸ptima a juzgar por el valor resultante:

    public static void main(String[] args) {
        // Same code as before with the addition of the values[] array
        System.out.println("Insert values: ");
        int[] values = new int[n + 1];
    
        for (int i=1; i <= n; i++) {
            values[i] = scanner.nextInt();
        }
    
        Element[][] elementMatrix = new Element[n + 1][k + 1];
    
        // A matrix that indicates how many newest objects are used
        // in the optimal solution.
        // Example: contains[5][10] indicates how many objects with
        // the weight of W[5] are contained in the optimal solution
        // for a knapsack of capacity K=10
        int[][] contains = new int[n + 1][k + 1];
    
        elementMatrix[0][0] = new Element(0);
    
        for (int i = 1; i <= n; i++) {
            elementMatrix[i][0] = new Element(0);
            contains[i][0] = 0;
        }
    
        for (int i = 1; i <= k; i++) {
            elementMatrix[0][i] = new Element(0);
            contains[0][i] = 0;
        }
    
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                elementMatrix[i][j] = new Element(elementMatrix[i - 1][j].getValue());
                contains[i][j] = 0;
    
                elementMatrix[i][j].setIncludes(false);
                elementMatrix[i][j].setValue(M[i - 1][j].getValue());
    
                if (j >= weights[i]) {
                    if ((elementMatrix[i][j - weights[i]].getValue() > 0 || j == weights[i])) {
                        if (elementMatrix[i][j - weights[i]].getValue() + values[i] > M[i][j].getValue()) {
                            elementMatrix[i][j].setIncludes(true);
                            elementMatrix[i][j].setValue(M[i][j - weights[i]].getValue() + values[i]);
                            contains[i][j] = contains[i][j - weights[i]] + 1;
                        }
                    }
                }
    
                System.out.print(elementMatrix[i][j].getValue() + "/" + contains[i][j] + "  ");
            }
    
            System.out.println();
        }
    
        System.out.println("Value: " + elementMatrix[n][k].getValue());
    }
    

    Salida:

    Insert knapsack capacity:
    12
    Insert number of items:
    5
    Insert weights:
    9 7 4 10 3
    Insert values:
    1 2 3 4 5
    0/0  0/0  0/0  0/0  0/0  0/0  0/0  0/0  0/0  1/1  0/0  0/0  0/0
    0/0  0/0  0/0  0/0  0/0  0/0  0/0  2/1  0/0  1/0  0/0  0/0  0/0
    0/0  0/0  0/0  0/0  3/1  0/0  0/0  2/0  6/2  1/0  0/0  5/1  9/3
    0/0  0/0  0/0  0/0  3/0  0/0  0/0  2/0  6/0  1/0  4/1  5/0  9/0
    0/0  0/0  0/0  5/1  3/0  0/0  10/2  8/1  6/0  15/3  13/2  11/1  20/4
    Value: 20
    

    Distancia de Levenshtein

    Otro muy buen ejemplo del uso de la programaci贸n din谩mica es Editar distancia o Distancia de Levenshtein.

    La distancia de Levenshtein para 2 cadenas Ay Bes el n煤mero de operaciones at贸micas que necesitamos usar para transformar Aen las Bcuales son:

    • Eliminaci贸n de caracteres
    • Inserci贸n de caracteres
    • Sustituci贸n de caracteres (t茅cnicamente es m谩s de una operaci贸n, pero en aras de la simplicidad, llam茅mosla operaci贸n at贸mica)

    Este problema se maneja resolviendo met贸dicamente el problema de las subcadenas de las cadenas iniciales, aumentando gradualmente el tama帽o de las subcadenas hasta que sean iguales a las cadenas iniciales.

    La relaci贸n de recurrencia que usamos para este problema es la siguiente:

    $$
    lev_ {a, b} (i, j) = minbegin {cases}
    lev_ {a, b} (i-1, j) +1 \ lev_ {a, b} (i, j-1) +1 \ lev_ {a, b} (i-1, j-1) + c (a_i, b_j) end {cases}
    $$

    c(a,b)siendo 0 si a==by 1 si a!=b.

    Si est谩 interesado en leer m谩s sobre la distancia de Levenshtein, ya lo hemos cubierto en Python en otro art铆culo: Distancia de Levenshtein y similitud de texto en Python

    Implementaci贸n

    public class editDistance {
        public static void main(String[] args) {
            String s1, s2;
            Scanner scanner = new Scanner(System.in);
            System.out.println("Insert first string:");
            s1 = scanner.next();
            System.out.println("Insert second string:");
            s2 = scanner.next();
    
            int n, m;
            n = s1.length();
            m = s2.length();
    
            // Matrix of substring edit distances
            // example: distance[a][b] is the edit distance
            // of the first a letters of s1 and b letters of s2
            int[][] distance = new int[n + 1][m + 1];
    
            // Matrix initialization:
            // If we want to turn any string into an empty string
            // the fastest way no doubt is to just delete
            // every letter individually.
            // The same principle applies if we have to turn an empty string
            // into a non empty string, we just add appropriate letters
            // until the strings are equal.
            for (int i = 0; i <= n; i++) {
                distance[i][0] = i;
            }
            for (int j = 0; j <= n; j++) {
                distance[0][j] = j;
            }
    
            // Variables for storing potential values of current edit distance
            int e1, e2, e3, min;
    
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    e1 = distance[i - 1][j] + 1;
                    e2 = distance[i][j - 1] + 1;
                    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                        e3 = distance[i - 1][j - 1];
                    } else {
                        e3 = distance[i - 1][j - 1] + 1;
                    }
                    min = Math.min(e1, e2);
                    min = Math.min(min, e3);
                    distance[i][j] = min;
                }
    
            }
    
            System.out.println("Edit distance of s1 and s2 is: " + distance[n][m]);
        }
    }
    

    Salida :

    Insert first string:
    man
    Insert second string:
    machine
    Edit distance of s1 and s2 is: 3
    

    Subsecuencia com煤n m谩s larga (LCS)

    El problema es el siguiente:

    Dadas dos secuencias, encuentre la longitud de la subsecuencia m谩s larga presente en ambas. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente contigua.

    Aclaraci贸n

    Si tenemos dos cadenas, s1 = "MICE"y s2 = "MINCE", la subcadena com煤n m谩s larga ser铆a “MI” o “CE”, sin embargo, la subsecuencia com煤n m谩s larga ser铆a “MICE” porque los elementos de la subsecuencia resultante no tienen que estar en orden consecutivo.

    Relaci贸n de recurrencia y l贸gica general

    $$
    lcs_ {a, b} (i, j) = minbegin {casos}
    lcs_ {a, b} (i-1, j) \ lcs_ {a, b} (i, j-1) \ lcs_ {a, b} (i-1, j-1) + c (a_i, b_j) end {cases}
    $$

    Como podemos ver, solo hay una peque帽a diferencia entre la distancia de Levenshtein y LCS, espec铆ficamente, en el costo de los movimientos.

    En LCS, no tenemos ning煤n costo por la inserci贸n y eliminaci贸n de caracteres, lo que significa que solo contamos el costo por sustituci贸n de caracteres (movimientos diagonales), que tienen un costo de 1 si los dos caracteres de cadena actuales a[i]y b[j]son iguales.

    El costo final de LCS es la longitud de la subsecuencia m谩s larga para las 2 cadenas, que es exactamente lo que necesit谩bamos.

    Usando esta l贸gica, podemos reducir muchos algoritmos de comparaci贸n de cadenas a relaciones de recurrencia simples que utilizan la f贸rmula base de la distancia de Levenshtein.

    Implementaci贸n

    public class LCS {
        public static void main(String[] args) {
            String s1 = new String("Hillfinger");
            String s2 = new String("Hilfiger");
            int n = s1.length();
            int m = s2.length();
            int[][] solutionMatrix = new int[n+1][m+1];
            for (int i = 0; i < n; i++) {
                solutionMatrix[i][0] = 0;
            }
            for (int i = 0; i < m; i++) {
                solutionMatrix[0][i] = 0;
            }
    
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    int max1, max2, max3;
                    max1 = solutionMatrix[i - 1][j];
                    max2 = solutionMatrix[i][j - 1];
                    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                        max3 = solutionMatrix[i - 1][j - 1] + 1;
                    } else {
                        max3 = solutionMatrix[i - 1][j - 1];
                    }
                    int tmp = Math.max(max1, max2);
                    solutionMatrix[i][j] = Math.max(tmp, max3);
                }
            }
            
            System.out.println("Length of longest continuous subsequence: " + solutionMatrix[n][m]);
        }
    }
    

    Salida :

    Length of longest continuous subsequence: 8
    

    Otros problemas que utilizan la programaci贸n din谩mica

    Hay muchos m谩s problemas que se pueden resolver con la programaci贸n din谩mica, estos son solo algunos de ellos:

    • Problema de partici贸n (pr贸ximamente)
    • Dado un conjunto de n煤meros enteros, averig眉e si se puede dividir en dos subconjuntos con sumas iguales
    • Problema de suma de subconjuntos (pr贸ximamente)
    • Dado un conjunto de n煤meros enteros positivos y una suma de valores, determine si hay un subconjunto del conjunto dado con una suma igual a la suma dada.
    • Problema de cambio de moneda (N煤mero total de formas de obtener la denominaci贸n de las monedas, pr贸ximamente)
    • Dado un suministro ilimitado de monedas de denominaciones determinadas, encuentre el n煤mero total de formas distintas de obtener el cambio deseado.
    • Total de posibles soluciones a la ecuaci贸n lineal de kvariables (pr贸ximamente)
    • Dada una ecuaci贸n lineal de kvariables, cuente el n煤mero total de posibles soluciones de la misma.
    • Encuentre la probabilidad de que un borracho no se caiga de un acantilado ( ni帽os, no intenten esto en casa )
    • Dado un espacio lineal que representa la distancia desde un acantilado, y siempre que conozca la distancia de inicio del borracho desde el acantilado y su tendencia a ir hacia el acantilado py alejarse del acantilado 1-p, calcule la probabilidad de su supervivencia.
    • Mucho mas…

    Conclusi贸n

    La programaci贸n din谩mica es una herramienta que puede ahorrarnos mucho tiempo computacional a cambio de una mayor complejidad espacial, dado que algunos de ellos solo van a la mitad (se necesita una matriz para la memorizaci贸n, pero se usa una matriz en constante cambio).

    Esto depende en gran medida del tipo de sistema en el que est茅 trabajando, si el tiempo de la CPU es valioso, opta por una soluci贸n que consume memoria, por otro lado, si su memoria es limitada, opta por una soluci贸n que consume m谩s tiempo para una mejor relaci贸n de complejidad tiempo / espacio.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *