dinámico de programación algoritmo de N, K problema

Question

Un algoritmo que tendrá dos números positivos N y K y calcular el mayor número posible podemos obtener mediante la transformación de N en otro número a través de la eliminación de los dígitos de N. K

Para ex, digamos que tenemos N = 12345 y K = 3, por lo que el mayor número posible que podemos obtener eliminando 3 dígitos de N es 45 (otras transformaciones serían 12, 15, 35 pero 45 es la más grande). Además, no puede cambiar el orden de los dígitos en N (entonces 54 NO es una solución). Otro ejemplo sería N = 66621542 y K = 3, por lo que la solución será 66654.

Sé que este es un problema relacionado con la programación dinámica y no puedo tener ni idea de cómo resolverlo. Necesito resolver esto por 2 días, así que cualquier ayuda es apreciada. Si no quiere resolver esto por mí, no tiene por qué hacerlo, pero sírvase indicarme el truco o al menos algunos materiales donde pueda leer más sobre algunos problemas similares.

Gracias de antemano.

Answer 1

El truco para resolver un problema de programación dinámica suele ser averiguar cómo es la estructura de una solución, y más específicamente si muestra óptima subestructura.

En este caso, me parece que la solución óptima con N = 12345 y K = 3 tendría una solución óptima para N = 12345 y K = 2 como parte de la solución. Si puede convencerse de que esto es válido, entonces debería poder expresar una solución recursiva al problema. Luego, impleméntalo con memoisation o bottom-up.

Answer 2

Esto es lo que pienso:

consideran la primera k + 1 dígitos de la izquierda. Busque el más grande, encuéntrelo y elimine los números a la izquierda. Si existen dos del mismo número más grande, busque el más a la izquierda y elimine los números a la izquierda de eso. almacena la cantidad de dígitos eliminados (nómbrelo j).

Haga lo mismo con el nuevo número como N y k + 1-j como K. Haga esto hasta que k + 1 -j sea igual a 1 (con suerte, si no me equivoco).

El número que terminará será el número que está buscando.

Answer 3

Los dos elementos más importantes de cualquier solución de programación dinámica son:

1. la definición del derecho subproblemas
2. Definir una relación recurrencia entre la respuesta a un sub-problema y la respuesta a los más pequeños sub-problemas
3. Encontrando casos base, los sub-problemas más pequeños cuya respuesta no depende de ninguna otra respuesta
4. averiguar el orden de exploración en el que debe resolver los subproblemas (para que nunca utiliza la relación de recurrencia en base a los datos sin inicializar)

Usted sabe que tiene los subproblemas derecha definido cuando

• el problema que necesita la respuesta a es uno de ellos
• los casos base realmente son triviales
• la recurrencia es fácil de evaluar
• El orden de exploración es sencillo

En su caso, es sencillo especificar los subproblemas. Dado que esto es probablemente una tarea, le daré la pista de que podría desear que N tuviera menos dígitos para comenzar con.

Answer 4

Bueno, para resolver cualquier problema de programación dinámica, debe dividirlo en subsoluciones recurrentes.

Digamos que definimos su problema como A (n, k), que devuelve el mayor número posible eliminando k dígitos de n.

Podemos definir un algoritmo recursivo simple a partir de esto.

Usando su ejemplo, A (12345, 3) = max {A (2345, 2), A (1345, 2), A (1245, 2), A (1234, 2)}

Más en general, A (n, k) = máximo {A (n con 1 dígito eliminado, k - 1)}

Y su caso base es A (n, 0) = n.

Usando este enfoque, puede crear una tabla que almacena en caché los valores de ny k.

int A(int n, int k) 
{ 
    typedef std::pair<int, int> input; 
    static std::map<input, int> cache; 

    if (k == 0) return n; 

    input i(n, k); 
    if (cache.find(i) != cache.end()) 
    return cache[i]; 

    cache[i] = /* ... as above ... */ 

    return cache[i]; 
} 

Ahora, esa es la solución recta hacia adelante, pero hay una mejor solución que funciona con una muy pequeña caché unidimensional. Considere reformular la pregunta de esta manera: "Dada una cadena ny un entero k, encuentre la subsecuencia lexicográficamente más grande en n de longitud k". Este es esencialmente su problema y la solución es mucho más simple.

Ahora podemos definir una función diferente B (i, j), lo que da la mayor secuencia lexicográfico de longitud (i - j), utilizando sólo los primeros i dígitos de n (en es decir, habiendo eliminado j dígitos del primer dígitos de n).

Usando su ejemplo de nuevo, tendríamos:

B (1, 0) = 1

B (2, 0) = 12

B (3, 0) = 123

B (3, 1) = 23

B (3, 2) = 3

etc.

Con un poco de pensamiento, podemos encontrar la relación de recurrencia:

B (i, j) = máx (10B (i-1, j) + n _i, B (i-1, j-1))

o, si j = i entonces B (i, j) = B (i-1, j-1)

y B (0, 0) = 0

Y usted puede codificar hasta que de una manera muy similar a la anterior.

Answer 5

Esto se puede resolver en O (L) donde L = número de dígitos. ¿Por qué utilizar fórmulas DP complicadas cuando podemos usar una pila para hacer esto:

Para: 66621542 Añadir un dígito en la pila mientras que hay menor o igual a L - K dígitos en la pila: 66621. Ahora, elimine los dígitos de la pila mientras son menores que el dígito leído actualmente y coloque el dígito actual en la pila:

lea 5: 5> 2, saque 1 de la pila. 5> 2, pop 2 también. poner 5: 6665 leer 4: la pila no está llena, poner 4: 66654 leer 2: 2 < 4, no hacer nada.

Necesita una condición más: asegúrese de no sacar más elementos de la pila que los dígitos que quedan en su número, de lo contrario su solución estará incompleta.

Otro ejemplo: 12345 L = 5, K = 3 put L - K = 2 dígitos en la pila: 12

de lectura 3, 3> 2, pop 2, 3> 1, pop 1, poner 3.pila: 3 lee 4, 4> 3, pop 3, pon 4: 4 lee 5: 5> 4, pero no podemos mostrar 4, de lo contrario no tendremos suficientes dígitos. así que presione 5: 45.