En la siguiente entrega, se pondrá a prueba lo aprendido durante la cursada trabajando en un problema en cuestión, en este caso el Problema de Varilla (Rod Cutting) el cual buscará ser resuelto mediante tres técnicas diferentes de resolución de paradigmas algorítmicos los cuales son Ávidos (Greedy), Programación Dinámica y Backtraking (Vuelta Atrás). En primer lugar se mostrará una presentación del escenario, su metodología, con ejemplos del mismo y seguido a este sus formas de resolverlo junto con los planteos y resultados obtenidos. Comenzaremos por la resolución mediante Ávidos utilizando un contraejemplo para su explicación, seguido de Programación Dinámica junto con la ecuación de recurrencia, la tabla y su código correspondiente y por último Backtraking con su árbol binario, nuestro planteo para su solución y su respectivo código. En cada caso se mostrará la complejidad de los algoritmos que conlleva cada técnica. Cabe destacar que el lenguaje de programación que utilizamos en cada caso es Python. Se anexará dentro del documento el hipervínculo al árbol de Backtraking, para una mejor visualización del mismo.
El problema de la varilla consta de una varilla de n centímetros de largo y una variedad de precios arbitrarios (no infiere que porque tenga más tamaño deba tener mayor costo) de todas las piezas de tamaño menores que n, siendo n valores enteros mayores a 1. El problema consiste en determinar el mayor valor que se puede obtener cortando la varilla y vendiendo las piezas.
🔴IMPORTANT: Ver documento Rod Cutting TPI para vas informacion 🔴❗