[pyar] Problemita

[Guillermo Garcia]

Hola, me parece que la mejor solución es mediante programación dinámica.
Si t es el triangulo y r el resultado, comenzas con r[1,1] = t[1,1] y luego
t[i,j] = max(t[i,j]+r[i-1,j-1],t[i,j]+r[i-1,j]).
El resultado es el maximo r. Podés tener una tabla adicional para guardar el
camino que recorrés para llegar a dicho r.
Saludos, Guillermo

2010/6/10 Marcos Moyano <marcos en anue.biz>

>    Hola lista,
> Les paso un problemita que me estuvo comiendo la cabeza un buen rato del
> día de hoy y lamentablemente no encontré una solución elegante. Por ahi
> algún valiente con ganas me tire una mano :-)
>
> A) Mirar el triangulo/grafo:
>    5
>   9 6
>  4 6 8
> 0 7 1 5
>
> B) Arrancando desde arriba (5) y moviéndonos para abajo a numeros
> adyacentes, vayamos sumándolos. La suma máxima es: 5 + 9 +  6 + 7 = 27
> (ejemplo de otros caminos posibles son: 5 + 6 + 8 + 5, 5 + 9 + 4 + 7, 5 + 6
> + 6 + 7, etc.) (Notar el último ejemplo)
>
> Alguien me tira una idea de como modelaría la estructura de manera que sea
> *simple* la solución?
> En la teoría todo bien. Podemos usar Dijkstra o A* y sale de pelos, pero no
> logro implementarlo de manera "sencilla".
>
> Desde ya, mil gracias a los valientes :-)
>
> salu2
> Marcos
>
> --
> Some people, when confronted with a problem, think “I know, I'll use
> regular expressions.” Now they have two problems.
>
> Jamie Zawinski, in comp.emacs.xemacs
>
> _______________________________________________
> pyar mailing list pyar en python.org.ar
> http://listas.python.org.ar/listinfo/pyar
>
> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20100610/646af6b2/attachment.html>