7.3.1. Problema de la mochila 0/1.

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

res.CI:= 0;

res.CS:= ?MochilaVoraz (1, M, v, w)?;

res.BE:= Mochila01Voraz (1, M, v, w);

res.nivel:= 0;

res.v_act:= 0; res.w_act:= 0;

Devolver res;

Generar (x: nodo; i: (0, 1); v, w: array [1..n] of int; M: int) : nodo;

res.tupla:= x.tupla;

res.nivel:= x.nivel + 1;

res.tupla[res.nivel]:= i;

Si i = 0 Entonces res.v_act:= x.v_act; res.w_act:= x.w_act;

Sino res.v_act:= x.v_act + v[res.nivel]; res.w_act:= x.w_act + w[res.nivel];

res.CI:= res.v_act;

res.BE:= res.CI + Mochila01Voraz (res.nivel+1, M - res.w_act, v, w);

res.CS:= res.CI + ?MochilaVoraz (res.nivel+1, M - res.w_act, v, w)?;

Si res.w_act > M Entonces { Sobrepasa el peso M: descartar el nodo }

res.CI:= res.CS:= res.BE:= -?;

Devolver res;

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica