Saltar al contenido principal
Z

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.

Gratis Sin registro Del lado del cliente Respetuoso con la privacidad Updated

/

Pseudocódigo

Press Run to animate the algorithm.

Cómo usar

  1. 1 Pulsa Run para rellenar la tabla de programación dinámica celda por celda.
  2. 2 Cada fila representa un objeto; cada columna representa una capacidad de 0 a W.
  3. 3 Cada celda toma el mejor valor entre descartar el objeto (celda azul de arriba) o incluirlo.
  4. 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.

Características

Animación de la tabla de PD

Observa cómo se llena la tabla de valores a medida que se consideran cada artículo y capacidad.

Complejidad

Tiempo y espacio: O(nW) (pseudo-polinómico). El problema es NP-difícil en general.

100% privado

Se ejecuta enteramente en tu navegador — no se sube nada.

Ejemplo

Input

items (w,v) = (10,60),(20,100),(30,120); capacity 50

Output

max value = 220 (take items 2 and 3, weight 50)

Casos de uso comunes

  1. 1

    Aprender programación dinámica

    Descubre cómo los subproblemas superpuestos construyen el valor óptimo.

  2. 2

    Asignación de recursos

    Modela la elección de artículos bajo un límite de peso o presupuesto.

  3. 3

    Comprensión de lo pseudo-polinómico

    Entiende por qué O(nW) no es realmente polinómico.

Resumen

El visualizador de la mochila 0/1 de Zerethon anima la solución de programación dinámica directamente en tu navegador, rellenando una tabla de mejores valores según cada artículo y la capacidad restante. Se ejecuta en tiempo O(nW) y espacio O(nW) (n artículos, capacidad W) — pseudo-polinómico, ya que W crece exponencialmente respecto a la longitud de sus bits; el problema de la mochila 0/1 es NP-difícil en general.

Categoría
Algoritmos
Precio
Gratis
Privacidad
Basado en el navegador
Registro
No necesario

Referencias

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 herramienta

Visualizador 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 herramienta

Visualizador 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 herramienta

Visualizador 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 herramienta

Crea, comparte y crece en Zerethon Social

Registro gratuito. Gana puntos, colecciona logros y conecta con creadores de todo el mundo.

Regístrate gratis