🎒 Problema de la Mochila - Guía Completa
📚 ¿Qué es el Problema de la Mochila?
El problema de la mochila (Knapsack Problem) es uno de los problemas clásicos más importantes en:
- 📊 Optimización: Maximizar o minimizar algo bajo restricciones
- 💻 Informática: Algoritmos y complejidad computacional
- 🏭 Investigación Operativa: Toma de decisiones
- 📦 Logística: Empaquetamiento y transporte
🎯 El Objetivo
Tienes una mochila con una capacidad máxima de peso. Tienes varios items, cada uno con:
- Peso: Cuánto ocupa
- Beneficio/Valor: Cuánto vale o te beneficia
Objetivo: Seleccionar items para llenar la mochila de manera que:
- ✅ El peso total NO exceda la capacidad máxima
- ✅ El beneficio total sea MÁXIMO
🔀 Variantes del Problema
📦 Mochila Binaria (0/1 Knapsack)
Cada item se puede incluir 0 o 1 vez. Es como preguntar: "¿Lo tomo o no lo tomo?"
- ✓ Lo tomas completo
- ✗ No lo tomas
- ✗ No puedes tomar la mitad
- ✗ No puedes tomar más de uno
📚 Mochila Múltiple (Unbounded Knapsack)
Cada item se puede incluir múltiples veces. Imagina que hay infinitas copias de cada item.
- ✓ Puedes tomar 0 unidades
- ✓ Puedes tomar 1 unidad
- ✓ Puedes tomar 2 unidades
- ✓ Y tantas más como quepan
⚡ Algoritmo Voraz (Greedy Algorithm)
Estrategia:
1. Calcula el RATIO para cada item: beneficio ÷ peso
2. Ordena los items por RATIO (mayor primero)
3. Toma items en ese orden mientras quepan
Pseudo-código:
items = ordenar_por_ratio(items)
para cada item en items:
si (peso_actual + item.peso ≤ capacidad):
agregar_item(item)
peso_actual += item.peso
📊 Ejemplo Práctico
Problema:
Mochila Binaria
Capacidad máxima: 10 kg
| Item |
Peso |
Beneficio |
Ratio (B/P) |
| 💻 Laptop |
3 kg |
20 |
6.67 |
| 📚 Libro |
2 kg |
10 |
5.00 |
| ⌚ Reloj |
1 kg |
6 |
6.00 |
| 📷 Cámara |
4 kg |
15 |
3.75 |
Solución Voraz:
- Ordena por ratio: Laptop (6.67) → Reloj (6.00) → Libro (5.00) → Cámara (3.75)
- Toma Laptop: peso = 3, beneficio = 20 ✓
- Toma Reloj: peso = 3+1 = 4, beneficio = 20+6 = 26 ✓
- Toma Libro: peso = 4+2 = 6, beneficio = 26+10 = 36 ✓
- Toma Cámara: peso = 6+4 = 10, beneficio = 36+15 = 51 ✓
- Resultado: Peso=10, Beneficio=51
⚠️ Importante: El algoritmo voraz es rápido pero NO siempre encuentra la solución óptima.
Es una "buena aproximación" que funciona bien en muchos casos pero puede fallar en otros.
🎮 Cómo Usar el Juego
1. Selecciona las Opciones
En el menú principal, elige:
- Tipo de problema: Binaria o Múltiple
- Dificultad: Fácil (50s), Medio (60s), Difícil (70s)
2. Juega
Arrastra items a la mochila antes de que termine el tiempo. Intenta maximizar el beneficio.
- Panel izquierdo: Items disponibles
- Centro: Tu mochila (arrastra aquí)
- Derecha: Información del problema
3. Compara Resultados
Al terminar el tiempo:
- Ver tu solución
- Ver la solución del algoritmo voraz
- Recibir retroalimentación
💡 Consejos para Jugar Bien
- Observa los ratios: Items con mayor beneficio/peso son más eficientes
- Calcula mentalmente: Suma rápido los pesos
- No llenes demasiado: A veces dejar espacio es estratégico
- Aprende del algoritmo: ¿Por qué eligió esos items?
- Intenta ganar: ¡Es posible ganarle al algoritmo voraz!
📈 Complejidad y Importancia
¿Por qué es importante este problema?
- 🎓 Es NP-completo (muy difícil de resolver óptimamente)
- 📦 Tiene aplicaciones reales: logística, inversión, manufactura
- 🔬 Enseña técnicas de optimización fundamentales
- 💻 Muchos algoritmos para resolverlo: voraz, DP, branch & bound
🔗 Enlaces Útiles
- Wikipedia:
Knapsack problem
- Algoritmos: Programación Dinámica, Algoritmos Voraces
- Aplicaciones: Asignación de recursos, inversión en proyectos
🎮 Volver al Juego