Tarea 4 FEDA - Fundamentos de Estructuras de Datos y Algoritmos

Este proyecto implementa tres algoritmos fundamentales y sus versiones optimizadas para resolver problemas relacionados con planificación de salas, minimización de costos de cajas y maximización de ganancias. Los algoritmos están diseñados para ser eficientes y escalables, utilizando estructuras de datos avanzadas y técnicas de optimización.

Resumen de Algoritmos

1. Planificación de Salas (Problema 1)

• Descripción: Este algoritmo determina el número mínimo de salas requeridas para programar un conjunto de actividades sin solapamiento temporal.
• Enfoque: Algoritmo greedy con ordenamiento y uso de min-heap (std::priority_queue)
• Optimización: La implementación utiliza un heap para acceso eficiente O(log n) en lugar de búsqueda lineal O(n)
• Complejidad: O(n log n) por el ordenamiento inicial + O(n log n) por las operaciones de heap
• Archivo: p1/p1.cpp, p1/p1.hpp

2. Minimización de Costos de Cajas (Problema 2)

• Descripción: Este algoritmo de programación dinámica minimiza el costo de cajas necesarias para almacenar un número específico de manzanas idénticas.
• Enfoque: Programación dinámica bottom-up con tabulación
• Optimización: La solución está optimizada para uso de memoria y maneja casos donde las cajas tienen mayor capacidad que el número objetivo
• Complejidad: O(N × M) donde N = número de manzanas, M = tipos de cajas
• Archivo: p2/p2.cpp, p2/p2.hpp

3. Maximización de Ganancias (Problema 3)

• Descripción: Este algoritmo maximiza el producto de elementos emparejados de dos listas mediante reordenamiento óptimo.
• Enfoque: Algoritmo greedy basado en la desigualdad de reordenamiento
• Optimización: Utiliza ordenamiento descendente para ambas listas y verificación por fuerza bruta
• Complejidad: O(n log n) por el ordenamiento
• Archivo: p3/p3.cpp, p3/p3.hpp

Estructura del Proyecto

tarea/
├── p1/                     # Problema 1: Planificación de Salas
│   ├── p1.cpp             # Implementación con min-heap optimizado
│   └── p1.hpp             # Definiciones de estructuras y clases
├── p2/                     # Problema 2: Minimización de Costos
│   ├── p2.cpp             # Programación dinámica bottom-up
│   └── p2.hpp             # Declaraciones de funciones DP
├── p3/                     # Problema 3: Maximización de Ganancias
│   ├── p3.cpp             # Algoritmo greedy + verificación fuerza bruta
│   └── p3.hpp             # Funciones de optimización y cálculo
├── data/                   # Casos de prueba y resultados
│   └── casos_prueba.txt  # Casos de prueba estructurados
│   
├── CMakeLists.txt         # Configuración de compilación
├── README.md              # Este archivo
└── main.cpp               # Une los problemas, lee los casos y mide el tiempo

Instrucciones de Configuración

Prerequisitos

• Compilador: GCC 7+ o Clang 8+ (soporte para C++17)
• CMake: Versión 3.10 o superior
• Sistema Operativo: Linux (Ubuntu/Debian recomendado)

Compilación

1. Clonar proyecto desde GitHub:

   git clone https://github.com/TU_USUARIO/tarea-4-feda.git
   cd tarea-4-feda

2. Crear directorio de compilación:

   mkdir build && cd build

3. Configurar con CMake:

   cmake ..

4. Compilar el proyecto:

   make -j$(nproc)

5. Ejecutar desde el directorio raíz:

   cd ..
   ./build/tarea-4

Ejecución de Algoritmos

./tarea-4 # Ejecuta todos los problemas

Ejecutar Problema 1 (Planificación de Salas)

# O compilar individualmente:
g++ -std=c++17 -O2 -I../p1 ../p1/p1.cpp main_p1.cpp -o p1_test
# Ejemplo: Actividades=[(1,10), (1,10), (1,10)]
# Resultado esperado: 3 salas

Ejecutar Problema 2 (Costos de Cajas)

# Ejemplo con datos del enunciado: N=10, M=4
# Capacidades: [4,3,6,2], Precios: [10,4,13,1]
# Resultado esperado: 10 pesos

Ejecutar Problema 3 (Maximización de Ganancias)

# Ejemplo: A=[2,3,5], B=[4,2,1]
# Resultado esperado: 11,250

Casos de Prueba

Los casos de prueba están definidos en data/casos_prueba.json:

Problema 1 - Casos Validados:

• Caso básico: 8 actividades → 4 salas mínimas
• caso alternativo: 3 actividades → 2 salas
• Sin solapamiento: 3 actividades → 1 sala
• Solapamiento total: 3 actividades idénticas → 3 salas

Problema 2 - Casos Validados:

• Ejemplo del enunciado: N=10, resultado = 5 pesos (usando 5 cajas tipo 4)
• Caso alternativo: N=7, resultado = 8 pesos

Problema 3 - Casos Validados:

• Caso óptimo: A=[2,3,5], B=[4,2,1] → ganancia = 11,250
• Caso trivial: A=[1,1,1], B=[1,1,1] → ganancia = 1

Contribuciones

Este proyecto es parte de la Tarea 4 del curso Fundamentos de Estructuras de Datos y Algoritmos (FEDA).

Licencia

Este proyecto está licenciado bajo la Licencia MIT. Ver el archivo LICENSE para detalles.

---

Curso: Fundamentos de Estructuras de Datos y Algoritmos
Institución: Universidad de Concepción Fecha: Julio 2025