Scribd
Cargar
21 vistas1 página

Knapsack

El documento detalla un proyecto para diseñar un algoritmo que resuelva el problema de la mochila utilizando programación dinámica. Se requiere analizar un algoritmo recursivo existente y optimizarlo, además de ejecutar el algoritmo con datos de prueba específicos. Finalmente, se debe evaluar la complejidad del algoritmo y presentar un reporte en formato PDF con el código y resultados.

Cargado por

sescobedo03
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
21 vistas1 página

Knapsack

El documento detalla un proyecto para diseñar un algoritmo que resuelva el problema de la mochila utilizando programación dinámica. Se requiere analizar un algoritmo recursivo existente y optimizarlo, además de ejecutar el algoritmo con datos de prueba específicos. Finalmente, se debe evaluar la complejidad del algoritmo y presentar un reporte en formato PDF con el código y resultados.

Cargado por

sescobedo03
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Ing.

Física
Programación II

Problema de la Mochila (Knapsack Problem)

Objetivo
Diseñar un algoritmo que resuelva por medio de programación dinámica el problema de la
mochila (Knapsack Problem).

Instrucciones
1. Analice el programa recursivo de Knapsack y proponga un algoritmo basado en
programación dinámica que resuelva el problema en tiempo polinomial.
2. Ejecute el algoritmo propuesto y determine un valor optimizado con los
siguientes valores:
# Datos de entrada para la prueba
weights = [9, 5, 7, 11, 4, 3, 13, 4, 12, 12, 20, 9, 2, 15, 18, 4, 13, 3, 18, 10, 20, 12,
19, 7, 3, 2, 8, 10, 3, 8, 4, 13, 9, 15, 12, 6, 12, 12, 7, 9, 3, 20, 6, 18, 8, 6, 15, 13,
9, 18]
values = [66, 93, 24, 68, 18, 90, 112, 78, 26, 64, 90, 64, 137, 111, 127, 46, 77,
45, 73, 147, 77, 119, 112, 102, 66, 45, 140, 136, 33, 22, 38, 49, 50, 118, 26, 108,
107, 129, 145, 74, 12, 39, 147, 78, 97, 38, 85, 121, 50, 126]
C = 100
n = len(weights)
3. ¿Cuál es la complejidad del algoritmo propuesto? Fundamente sus
conclusiones.

Herramientas
Usar un IDE (Integrated Development Environment) para facilitar el manejo y visualización
del código (Eclipse, PyCharm, Spyder, etc.) y librerías para graficar, como matplotlib.

Entrega
Se deberá subir un reporte en formato PDF al campus virtual con el siguiente contenido:
1. Portada.
2. Código documentado (comentarios en cada sección y en las líneas de código en
que sea necesario).
3. Resultados de las instrucciones.

Dr. Saúl Tovar Arriaga

También podría gustarte