7.3.1. Problema de la mochila 0/1.

Mochila01RyP (v, w: array [1..n] of integer; M: integer; var s: nodo);

inic:= NodoInicial (v, w, M);

C:= inic.CI;

LNV:= {inic};

s.v_act:= -?;

Mientras LNV ? ? hacer

x:= Seleccionar (LNV); { Según el criterio MB-LIFO }

LNV:= LNV - {x};

Si x.CS > C Entonces { Si no se cumple se poda x }

Para i:= 0, 1 Hacer

y:= Generar (x, i, v, w, M);

Si (y.nivel = n) Y (y.v_act > s.v_act) Entonces

s:= y;

C:= max (C, s.v_act );

Sino Si (y.nivel < n) Y (y.CS > C) Entonces

LNV:= LNV + {y};

C:= max (C, y.CI );

FinPara;

FinSi;

FinMientras;

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica