“¿Cómo hacemos la parte de retroceso …”
Por “retroceder”, quiere decir:
- un algoritmo de retroceso / fuerza bruta para resolver todo el problema, o
- ¿Una forma de recuperar la secuencia de decisiones tomadas por un algoritmo de Programación Dinámica (DP) (para que pueda imprimirlas)?
Si es el primer caso: ¡no use un algoritmo de retroceso / fuerza bruta! Cada operación deja una matriz / subproblema más pequeño. Esta subestructura recursiva sugiere un algoritmo DP.
- ¿Cuál es la diferencia entre tener un buen algoritmo y no tener uno?
- ¿Cuál es su opinión sobre Interview Cake para resolver algoritmos?
- ¿Cómo puede el paralelismo mejorar el algoritmo de fuerza bruta?
- ¿Qué se siente al resolver bien los problemas de programación dinámica?
- ¿Por qué el algoritmo RSA no lleva el nombre de Ellis, Cocks y Williamson, dado que lo inventaron primero?
Una vez que tenga un algoritmo DP, recuperar las decisiones es una cuestión de “rastrear” el algoritmo (recursivamente). Esto generalmente depende de su prueba de corrección: la mayoría de estas pruebas son constructivas y muestran cómo realmente construiría la solución.
En mi caso, mi DP es como un algoritmo de “mochila modificada”. Decido si el signo entre cada número es positivo (+) o negativo (-). La única advertencia es que el primer signo debe ser negativo. Entonces, si se dan números [matemáticas] [2,3,5,7] [/ matemáticas], entonces debo decidir si es
- [matemáticas] 2-3 + 5 + 7 = 11 [/ matemáticas]
- [matemáticas] 2-3 + 5-7 = -3 [/ matemáticas]
- [matemáticas] 2-3-5 + 7 = 1 [/ matemáticas]
- [matemáticas] 2-3-5-7 = -13 [/ matemáticas].
Puedo demostrar que cualquier solución de este tipo a mi problema de “mochila” proporciona una solución al problema original y viceversa. Mi prueba realmente muestra cómo transformar uno en el otro, y en realidad me muestra cómo recuperar los pasos de mi algoritmo DP, todo a la vez.
Bosquejo rápido de prueba:
Dada una solución al problema de la mochila, observe el signo “-” más a la derecha (al menos existirá uno, ya que el primer signo será negativo). Envuelva todo después de ese signo entre paréntesis y “voltee” (esto no cambia el valor). Repita todo antes del signo (generando una secuencia de instrucciones), imprima las instrucciones “simples” para todo después del signo y luego imprima una instrucción más para combinarlas.
Código:
Echa un vistazo a mi esencia para obtener una explicación y un código más completos:
SPOJ – MENOS (http://www.spoj.com/problems/MINUS/)
