7.3.1. Problema de la mochila 0/1.

• Forma de realizar la poda:

  • En una variable C guardar el valor de la mayor cota inferior hasta ese momento dado.
  • Si para un nodo, su cota superior es menor o igual que C entonces se puede podar ese nodo.

• Estrategia de ramificación:

  • Puesto que tenemos una estimación del coste, usar una estrategia LC: explorar primero las ramas con mayor valor esperado (MB).
  • ¿LC-FIFO ó LC-LIFO? Usaremos la LC-LIFO: en caso de empate seguir por la rama más profunda. (MB-LIFO)

type nodo = record

v_act, w_act: integer;

CI, BE, CS: integer;

tupla: array [1..n] of integer;

nivel: integer;

end;

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica