Saltar al contenido principal
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

Dynamic Programming Visualizer

0/1 Knapsack

Paso 0 / 0
Speed 100ms
Step Progress 0 / 0
Table Size 0×0
Cells Filled 0
Status Ready
Uncomputed
Filling
Optimal path
0 / base case
Step Explanation

Select an algorithm and press Play to watch the table fill in.

—
Pseudocode 
 
 
 
 
  
 
 
Knapsack Problem
  
 
  Intermediate (3/5)
 
~1 hora   0/1 knapsack: take or leave  DP table: value vs weight capacity  Optimal substructure  Pseudo-polynomial time  
Prereqs: Programación dinámica, Arreglos 2D  
 
Quick Reference
0/1 Knapsack
The 0/1 Knapsack problem asks: given items with weight and value, and a capacity, choose a subset that maximizes total value without exceeding the capacity. Each item is taken whole (0 or 1 times).

Difficulty: Intermediate (3/5)
dp
Complexity
Best Time
O(nW)
Average Time
O(nW)
Worst Time
O(nW)
Space
O(nW)
When to Use
Use for resource-allocation problems with indivisible items: budgeting, cargo loading, and subset-selection optimization.
Pros
  • Exact optimal solution via DP
  • Pseudo-polynomial O(nW) — practical for modest capacities
  • Foundation for many optimization problems
Cons
  • Not polynomial in the input size (NP-hard in general)
  • O(nW) memory can be large
  • No good for huge capacities or fractional items
History
The knapsack problem was formulated in 1897 by mathematician George Bernard Mathews. The dynamic-programming solution became canonical after Richard Bellman developed the DP framework in the 1950s.
 
 
Knapsack Problem es el problema de programación dinámica clásico: dado un conjunto de items con peso y valor, y una mochila de capacidad W, selecciona el subconjunto que maximiza el valor total sin exceder la capacidad.


La versión 0/1 (cada item se toma o se deja) es ideal para DP: la decisión sobre el item i depende de la decisión óptima para la capacidad restante usando items 0..i-1.


Cómo Funciona


    

  1. Inicializa tabla DP: dp[i][w] = valor máximo usando items 0..i con capacidad w.
    2. 

  2. Recurre: para cada item i y capacidad w:

      

    • “Excluir: dp[i-1][w]”
      • 

    • “Incluir: value[i] + dp[i-1][w - weight[i]] (si cabe)”
      • 

    • dp[i][w] = max(excluir, incluir)
      • 

    

    3. 

  3. Resultado: dp[n][W]
    4. 



Idea Clave


La optimal substructure es clave: la decisión óptima para capacidad w usando items 0..i depende solo de decisiones óptimas para capacidades menores usando items 0..i-1. Eso llena una tabla 2D de n × W.


Greedy falla porque tomar el item de mejor ratio valor/peso puede bloquear una combinación superior. Ejemplo: {valor=100, peso=50} vs {valor=60, peso=20}, {valor=60, peso=20} — greedy toma el de ratio 2.0, pero los dos de ratio 3.0 suman 120.


Ejemplo Trabajado


Items: A(v=60, w=10), B(v=100, w=20), C(v=120, w=30), capacidad W=50.


Tabla DP (filas = items, columnas = capacidad 0..50):


    

  • “Sin items: todo 0”
    • 

  • “Item A (w=10): capacidades 0-9 = 0, 10-50 = 60”
    • 

  • “Item B (w=20):”

      

    • “w < 10: 0”
      • 

    • “w 10-19: 60 (A cabe, B no)”
      • 

    • “w 20-29: max(60, 100) = 100”
      • 

    • “w 30-49: max(60, 160) = 160 (A+B)”
      • 

    

    • 

  • “Item C (w=30):”

      

    • “w < 10: 0”
      • 

    • “w 10-19: 60”
      • 

    • “w 20-29: 100”
      • 

    • “w 30-39: max(160, 120) = 160”
      • 

    • “w 40-49: max(160, 180) = 180 (B+C: 100+120=220? No, w=20+30=50 > 40)”
      • 

    • “w 50: max(160, 60+120=180) = 180 (A+C: 10+30=40 ≤ 50)”
      • 

    

    • 



Resultado: dp[3][50] = 180 (items A y C: 60+120=180, peso 10+30=40).


Casos Extremos y Trampas


    

  • Pseudo-polinomial — O(nW) no es polinomial en el tamaño de entrada (W está en valor, no en bits). Para W grande, es lento.
    • 

  • Greedy — falla como se mostró. Solo funciona para fractional knapsack (puedes tomar fracciones).
    • 

  • Espacio — se puede reducir a O(W) con DP 1D (iterar capacidad hacia atrás).
    • 

  • Muchos items, W enorme — considerar meet-in-the-middle (O(2^{n/2})) o FPTAS.
    • 



Variantes
































VarianteRestricciónComplejidad
0/1 KnapsackTake or leaveO(nW) DP
UnboundedRepetir itemsO(nW) DP (forward)
Boundedk copias por itemO(nW) con binary splitting
FractionalTomar fraccionesGreedy O(n log n)


Aplicaciones


    

  • Optimización de recursos — presupuesto, asignación de memoria
    • 

  • Selección de proyectos — invertir en proyectos con retorno limitado
    • 

  • Cryptografía — subset sum como caso especial
    • 

  • Enseñanza — introduce DP 2D y optimal substructure
    • 



Trayectoria de Práctica


    

  1. Implementa 0/1 knapsack con tabla 2D; traza el ejemplo anterior.
    2. 

  2. Optimiza a 1D; explica por qué iteras w hacia atrás.
    3. 

  3. Muestra un contraejemplo donde greedy falla.
    4. 

  4. Extiende a unbounded knapsack: dp[w] = max(dp[w], dp[w-weight[i]] + value[i]).
    5. 

  5. Investiga FPTAS: ¿cómo aproximar la solución en tiempo polinomial?
    6.