Visualizador de la Mochila 0/1
Programación dinámica (dynamic programming) para el problema de la mochila 0/1 en forma de animación — rellena la tabla DP celda por celda, resaltando las celdas de las que depende cada una, con controles paso a paso. Se ejecuta directamente en el navegador.
Pseudocódigo
Press Run to animate the algorithm.
Time · Space
Cómo usar
- 1 Pulsa Run para rellenar la tabla de programación dinámica celda por celda.
- 2 Cada fila representa un objeto; cada columna representa una capacidad de 0 a W.
- 3 Cada celda toma el mejor valor entre descartar el objeto (celda azul de arriba) o incluirlo.
- 4 La celda de la esquina inferior derecha es el mejor valor alcanzable. Pulsa Shuffle para generar un nuevo conjunto de objetos.
Por qué usar esta herramienta
- Observa cómo se resuelve el problema de la mochila 0/1 mediante programación dinámica, en lugar de fuerza bruta (brute force).
- Comprueba cómo se construye cada celda a partir de las dos celdas de las que depende.
- Entiende por qué el tiempo de ejecución O(n·W) es muy superior a la complejidad exponencial de la fuerza bruta.
- Se ejecuta completamente en tu navegador. Sin registro, sin subir archivos.
Preguntas frecuentes
¿Qué es el problema de la mochila 0/1?
Dados varios objetos, cada uno con un peso y un valor, y una capacidad W, hay que elegir un subconjunto (cada objeto se toma una vez o no se toma) que maximice el valor total sin superar W.
¿Cómo funciona la tabla DP?
dp[i][w] es el mejor valor posible usando los primeros i objetos con capacidad w. Cada celda equivale a max(descartar el objeto = dp[i-1][w], incluirlo = dp[i-1][w-wi] + vi).
¿Cuál es la complejidad temporal?
Tiempo O(n·W) y espacio O(n·W) (que puede reducirse a O(W)). Se trata de una complejidad pseudopolinomial (pseudo-polynomial) — eficiente cuando W es pequeño.
¿Por qué se llama mochila 0/1?
Cada objeto se toma por completo (1) o se descarta (0) — no se puede tomar una parte de él, a diferencia de la mochila fraccionaria (fractional knapsack), que se resuelve con un enfoque voraz (greedy).
¿Qué es Visualizador de la Mochila 0/1?
El Visualizador de la Mochila 0/1 anima el llenado de la tabla de programación dinámica, donde dp[i][w] es el mejor valor posible usando los primeros i objetos con una capacidad w, calculado como el máximo entre descartar el objeto o incluirlo. La celda de la esquina inferior derecha contiene el valor óptimo.
Visualizador de la Mochila 0/1 es una utilidad algoritmos gratuita de Zerethon Tools. Programación dinámica (dynamic programming) para el problema de la mochila 0/1 en forma de animación — rellena la tabla DP celda por celda, resaltando las celdas de las que depende cada una, con controles paso a paso. Se ejecuta directamente en el navegador. Funciona totalmente en el navegador — sin registro, sin subida de archivos.
- Categoría
- Algoritmos
- Precio
- Gratis
- Privacidad
- Basado en el navegador
- Registro
- No necesario
Privacidad
Tus datos nunca salen de tu navegador, salvo que se indique explícitamente. Visualizador de la Mochila 0/1 funciona completamente del lado del cliente — sin subida a servidor, sin registro de actividad, sin seguimiento de tu contenido.
¿Nuevo en esto? Lee la explicación paso a paso con análisis de Big-O: Aprender Dynamic Programming →
Herramientas relacionadas
Visualizador de Bubble Sort
Simulación animada de bubble sort con controles paso a paso, velocidad ajustable, datos de entrada personalizados, contadores de comparaciones/intercambios en tiempo real y pseudocódigo. Se ejecuta completamente en tu navegador.
Abrir herramientaVisualizador de Insertion Sort
Insertion Sort animado con controles de reproducción paso a paso, velocidad ajustable, datos de entrada personalizados, contadores en vivo de comparaciones/escrituras y pseudocódigo. Se ejecuta completamente en tu navegador.
Abrir herramientaVisualizador de Selection Sort
Selection Sort animado con controles paso a paso, velocidad ajustable, entrada de datos personalizada, contadores de comparaciones/intercambios en vivo y pseudocódigo. Funciona completamente en tu navegador.
Abrir herramientaVisualizador de Merge Sort
Simulación animada de merge sort con controles paso a paso, velocidad ajustable, datos de entrada personalizados, contadores en vivo de comparaciones/escrituras y pseudocódigo. Funciona totalmente en el navegador.
Abrir herramientaCrea, comparte y crece en Zerethon Social
Registro gratuito. Gana puntos, colecciona logros y conecta con creadores de todo el mundo.