6.3.1. Problema de la mochila 0/1.
Para calcular el peso y el beneficio en cada nodo podemos usar variables locales w_act, v_act que guardarán el peso y el beneficio acumulado.
El array de soluciones será s: array [1..n] of integer.
- s[i] = 1, 0. Se añade o no se añade el objeto i.
- s[i] = -1. No se ha considerado el objeto i (es el valor de inicialización).
Funciones:
- Generar (nivel, s). Probar los valores 0 y 1.
Si s[nivel]=-1 entonces Devolver 0;
Sino w_act:= w_act + w[nivel];
v_act:= v_act + v[nivel];
Devolver 1;
- Solución (nivel, s). Indica los nodos hoja que cumplen la restricción de peso.
Devolver (nivel=n) and (w_act ? M);
- Criterio (nivel, s). Indica si se cumple la restricción de peso y no es una hoja.
Devolver (w _act ? M) and (nivel<n);
- MasHermanos (nivel, s).
Devolver s[nivel] ? 1;
- Retroceder (nivel, s).
w_act:= w_act - s[nivel]*w[nivel];
v_act:= v_act - s[nivel]*v[nivel];
s[nivel]:= -1;
nivel:= nivel - 1;