Skip to main content

Abrir el simulador

Mochila 0/1 y descomposición en sumandos en C: árbol de búsqueda con podas, todas las soluciones, una o la óptima.
Muchos problemas consisten en tomar una serie de decisiones: qué objetos meter en una mochila, qué casilla rellenar en un sudoku, dónde colocar cada reina en un tablero. Probar todas las combinaciones es inviable, pero muchas se pueden descartar a medio camino. El backtracking (vuelta atrás) explora las decisiones una a una y retrocede en cuanto una opción ya no puede llevar a una solución.

​
Lo que vas a aprender

  • El esquema general de backtracking.
  • El árbol de búsqueda y cómo se recorre.
  • Qué es una poda y por qué ahorra tanto trabajo.
  • Las tres variantes: todas las soluciones, una o la óptima.

​
Cómo se usa el simulador

  • Elige el problema: mochila 0/1 o descomposición en sumandos.
  • Elige la variante: todas las soluciones, una solución o la óptima.
  • Datos: número de objetos (2 – 5), capacidad y la tabla de pesos y beneficios.
  • Avanza con ⏮, ◀, ▶ Ejecutar, ▶ y ⏭. Se resaltan la línea del código en C, el vector de decisiones y el árbol de búsqueda (nodo actual, podado o solución). Los contadores dan los nodos generados, los podados y las soluciones.

​
Fundamentos teóricos

​
El esquema

La solución es un vector de decisiones x[1],x[2],…,x[n]x[1], x[2], \dots, x[n]. En cada nivel kk se prueban todas las opciones para x[k]x[k]:

​
El árbol de búsqueda

Cada nivel es una decisión y cada hoja, una secuencia completa. En la mochila 0/1, cada objeto tiene dos ramas (fuera o dentro): 2n2^n hojas.

​
Podas

Si una solución parcial ya no puede ser correcta, no se exploran sus descendientes. En la mochila: si el peso ya supera la capacidad, se corta la rama. En la variante óptima también se puede podar si ni metiendo todos los objetos restantes se superaría el mejor beneficio encontrado.

​
Las tres variantes

​
Coste

En el peor caso, el tamaño del árbol: exponencial (2n2^n en la mochila). Las podas no cambian el peor caso, pero en la práctica reducen muchísimo el trabajo.

​
Ejemplos resueltos

Ejemplo 1 · Mochila 0/1

Capacidad 8. Pesos 3, 4, 2, 5 y beneficios 8, 10, 3, 12.Hay 24=162^4 = 16 combinaciones. Se podan las que pesan más de 8 (por ejemplo, objetos 1, 2 y 3: peso 9).Algunas válidas: (1, 0, 0, 1) pesa 8 y vale 20; (1, 1, 0, 0) pesa 7 y vale 18; (0, 1, 1, 0) pesa 6 y vale 13.Óptima: objetos 1 y 4, beneficio 20.
Sin podas, el árbol completo de 4 objetos tiene 1+2+4+8+16=311 + 2 + 4 + 8 + 16 = 31 nodos. Con capacidad 8, todas las ramas que empiezan por meter los objetos 1 y 2 (peso 7) se cortan en cuanto se añade otro objeto.

​
Experimenta con el simulador

1

Podas

Con la mochila, baja la capacidad. ¿Aumentan los nodos podados?
2

Variantes

Compara los nodos generados para “todas”, “una” y “la óptima”.
3

Descomposición

Cambia al problema de descomposición y mira cómo se construyen las soluciones.

​
Errores frecuentes

  • No deshacer la decisión al volver atrás cuando se usan variables acumuladas (como el peso actual).
  • Podar demasiado pronto y perder soluciones válidas.
  • Confundir backtracking con fuerza bruta: la diferencia está en las podas.

​
Herramientas relacionadas

Recursión

Funciones que se llaman a sí mismas.

Combinatoria

Cuántas combinaciones hay.

Recorridos de grafos

DFS, una exploración en profundidad.
Última modificación el 6 de octubre de 2026