Complejidad Temporal
O(n × W)
El Problema de la Mochila 0/1: dados artículos con pesos y valores, y una capacidad máxima, encontrar el valor máximo que se puede transportar sin exceder la capacidad. Cada artículo puede tomarse como máximo una vez.
Cómo funciona (DP Bottom-Up):
1. Crear una tabla 2D: dp[i][w] = valor máximo usando los primeros i artículos con capacidad w
2. Para cada artículo i y capacidad w:
- Si el artículo no cabe: dp[i][w] = dp[i-1][w]
- Si cabe: dp[i][w] = max(dp[i-1][w], dp[i-1][w-peso[i]] + valor[i])
3. dp[n][W] contiene el valor óptimo
Complejidad Temporal: O(n × W) — pseudo-polinomial
Complejidad Espacial: O(n × W) — optimizable a O(W)
Aplicaciones:
- Asignación de recursos
- Planificación de presupuestos
- Carga de mercancías
- Criptografía
El Problema de la Mochila es uno de los problemas fundamentales en optimización combinatoria y es NP-duro en general.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Problema de la Mochila 0/1?
- El Problema de la Mochila 0/1: dados artículos con pesos y valores, y una capacidad máxima, encontrar el valor máximo que se puede transportar sin exceder la capacidad. Cada artículo puede tomarse como máximo una vez.
- ¿Cuál es la complejidad de Problema de la Mochila 0/1?
- Tiempo (promedio): O(n × W) · Espacio: O(n × W)
- ¿Para quién es este visualizador de Problema de la Mochila 0/1?
- La visualización de Problema de la Mochila 0/1 está pensada para nivel avanzado, dentro de la categoría Programación Dinámica. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Problema de la Mochila 0/1?
- En la misma categoría (Programación Dinámica) puedes explorar: Fibonacci DP, Longest Common Subsequence. Todos tienen visualización interactiva.