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

DP table animation

Watch the value table fill in as each item and capacity are considered.

Complexity

Time & space: O(nW) (pseudo-polynomial). The problem is NP-hard in general.

100% private

Runs entirely in your browser — nothing is uploaded.

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

    Learn dynamic programming

    See how overlapping subproblems build the optimal value.

  2. 2

    Resource allocation

    Model choosing items under a weight or budget limit.

  3. 3

    Pseudo-polynomial insight

    Understand why O(nW) isn't truly polynomial.

Resumen

Zerethon's 0/1 knapsack visualizer animates the dynamic-programming solution in your browser, filling a table of best values by item and remaining capacity. It runs in O(nW) time and O(nW) space (n items, capacity W) — pseudo-polynomial, since W is exponential in its bit length; the 0/1 knapsack problem is NP-hard in general.

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

References

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