UAX · Estructura de datos y algoritmos II · branch and bound
Branch and bound, paso a paso
La mochila 0/1 de las diapositivas: cuatro objetos y una capacidad. En cada nivel del árbol se decide si un objeto entra (✓) o no (✗). El backtracking solo poda lo que ya no cabe; el branch and bound calcula además una cota optimista de cada rama y la poda si ni así puede mejorar la mejor mochila encontrada.
El árbol de decisión
140·6 valor · peso≤156 cota nodo que se está mirando en la cola, esperando podado por cota no cabe (poda por peso) mejor mochila hasta ahora
Paso 0
Pulsa Ejecutar y avanza solo, o ve paso a paso con Siguiente (o con las flechas del teclado).