Esquemas generales

Existen tres esquemas para obtener:

• TODAS LAS SOLUCIONES FACTIBLES

• UNA SOLUCIÓN FACTIBLE

• SOLUCIÓN ÓPTIMA

Esquema general recursivo: “Todas soluciones factibles”

Esquema general iterativo: “Todas las soluciones factibles”

Esquema general recursivo: “Una solución factible”

Esquema general iterativo: “Una solución factible”

Esquema general recursivo: “La solución óptima”

Esquema general iterativo: “La solución óptima”

Ejemplo: Mochila

Restricciones explícitas: $(\forall i)(x_i \in {0,1}:1 \le i \le n)$

Procedimiento Mochila_TODAS (P[1..n]:vector de enteros, n, C, k:entero, e/s x[1..n]: vector de enteros)
 # Llamada inicial: Mochila_TODAS (P, n, C, 1, x)
      x[ k ] = - 1
      mientras x[ k ] < 1 hacer
	x[ k ] = x[ k ] + 1
	opción
		k = n and PESO(P, x, k) <= C: imprimir(x)
		k < n and PESO(P, x, k) <= C: Mochila_TODAS (P, n, C, k+1, x)
	fopción
      fmientras
fprocedimiento

Función PESO (P[1..n]:vector de enteros, x[1..n]:vector de enteros, k:entero) retorna (p:entero)
      var   i, peso_acumulado : entero fvar
      i = 0
      peso_acumulado = 0
      mientras (i < k) hacer
	i = i + 1
	peso_acumulado = peso_acumulado + P[i] * x[i]
      fmientras
      retorna peso_acumulado
ffuncion