Esquemas generales

Existen tres esquemas para obtener:

  • TODAS LAS SOLUCIONES FACTIBLES

  • UNA SOLUCIÓN FACTIBLE

  • SOLUCIÓN ÓPTIMA

Ejemplo: Mochila

Restricciones explícitas: (i)(xi0,1:1in)(\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

Last updated