## ACTIVIDAD10 AUTOEVALUACIÓN

## Repaso de la Unidad II

Descripción

Los ejercicios que se proponen tienen la finalidad de que realices un repaso de los temas de la Unidad II.

1. Tenemos n objetos de pesos p1,...,pn y valores v1,...,vn y una mochila de capacidad C. Escriba y analice un algoritmo que determine un subconjunto de objetos cuyo peso total no exceda la capacidad de la mochila y cuyo valor total sea maximal. Todas las cantidades C, vi y pi para i=1,...,n son números naturales.

2. Escribe la recurrencia que sirve de fundamento para la aplicación de la técnica de programación dinámica al problema de minimización del número de productos escalares en la multiplicación de una serie de matrices A1A2...An.
El algoritmo que resuelve este problema calcula una tabla factor (1..n,1..n) tal que factor (i,j)=k si la factorización óptima es (Ai...Ak)(Ak+1...Aj). Escribe y analiza un algoritmo que, a partir de factor (1..n,1..n), imprima la parentización óptima del producto A1A2...An.

3. Un arreglo T contiene n números naturales distintos. Queremos conocer los menores m números de T. Sabemos que m es mucho menor que n. ¿Cómo lo harías para que resultara más eficiente?. Justifica tu respuesta contrastando en tu estudio los análisis de caso peor y caso medio conocidos.

Valor 0%

###