Solución del problema de la mochila 0/1 mediante un ejemplo de programación dinámica

¿Qué es el problema de la mochila?

Problema de la mochila El algoritmo es un problema muy útil en combinatoria. En el supermercado hay n paquetes (n ≤ 100) el paquete i tiene un peso W[i] ≤ 100 y un valor V[i] ≤ 100. Un ladrón irrumpe en el supermercado, el ladrón no puede llevar un peso superior a M (M ≤ 100 ). El problema a resolver aquí es: ¿qué paquetes se llevará el ladrón para obtener el mayor valor?

Entrada:

  • Peso máximo M y número de bultos n.
  • Matriz de pesos W[i] y valor correspondiente V[i].

Salida:

  • Maximizar el valor y el peso correspondiente en capacidad.
  • Qué paquetes se llevará el ladrón.

El algoritmo de mochila se puede dividir en dos tipos:

  • El problema de la mochila 0/1 mediante programación dinámica. En este tipo de algoritmo de mochila, cada paquete se puede tomar o no. Además, el ladrón no puede tomar una fracción del paquete robado ni tomar un paquete más de una vez. Este tipo se puede resolver mediante el enfoque de programación dinámica.
  • Algoritmo del problema de mochila fraccionaria. Este tipo se puede resolver mediante una estrategia codiciosa.

Cómo resolver el problema de la mochila usando programación dinámica con ejemplo

En la estrategia de divide y vencerás, el problema a resolver se divide en subproblemas. Los subproblemas se dividen a su vez en subproblemas más pequeños. Esa tarea continuará hasta que obtenga subproblemas que puedan resolverse fácilmente. Sin embargo, en el proceso de dicha división, es posible que se encuentre con el mismo problema muchas veces.

La idea básica de la programación dinámica Knapsack es utilizar una tabla para almacenar las soluciones de los subproblemas resueltos. Si vuelve a enfrentar un subproblema, solo necesita tomar la solución de la tabla sin tener que resolverlo nuevamente. Por tanto, los algoritmos diseñados mediante programación dinámica son muy efectivos.

Resuelva el problema de la mochila mediante programación dinámica

Para resolver un problema mediante programación dinámica, debe hacer lo siguientewing Tareas:

  • Encuentre soluciones de los subproblemas más pequeños.
  • Descubra la fórmula (o regla) para construir una solución de subproblema mediante soluciones de subproblemas incluso más pequeños.
  • Cree una tabla que almacene las soluciones de los subproblemas. Luego calcule la solución del subproblema de acuerdo con la fórmula encontrada y guárdela en la tabla.
  • De los subproblemas resueltos se encuentra la solución del problema original.

Analizar el problema de la mochila 0/1

Al analizar el problema de la mochila 0/1 utilizando la programación dinámica, puede encontrar algunos puntos notables. El valor del algoritmo de mochila depende de dos factores:

  1. ¿Cuántos paquetes se están considerando?
  2. El peso restante que puede almacenar la mochila.

Por lo tanto, tienes dos cantidades variables.

Con la programación dinámica tienes información útil:

  1. la función objetivo dependerá de dos cantidades variables
  2. la tabla de opciones será una tabla bidimensional.

Si llamar a B[i][j] es el valor máximo posible seleccionando en paquetes {1, 2,…, i} con límite de peso j.

  • El valor máximo cuando se selecciona en n paquetes con el límite de peso M es B[n][M]. En otras palabras: Cuando hay i paquetes para elegir, B[i][j] es el peso óptimo cuando el peso máximo de la mochila es j.
  • El peso óptimo es siempre menor o igual que el peso máximo: B[i][j] ≤ j.

Por ejemplo: B[4][10] = 8. Significa que en el caso óptimo, el peso total de los paquetes seleccionados es 8, cuando hay 4 primeros paquetes para elegir (1er a 4to paquete) y el peso máximo de la mochila es 10. No es necesario que se seleccionen los 4 artículos.

Fórmula para calcular B[i][j]

Entrada, usted define:

  • W[i], V[i] son ​​a su vez el peso y el valor del paquete i, en el que i Fórmula para calcular B[i][j]{1,…,n}.
  • M es el peso máximo que puede llevar la mochila.

En el caso de simplemente tener solo 1 paquete para elegir. Calculas B[1][j] por cada j: lo que significa el peso máximo de la mochila ≥ el peso del 1er paquete

B[1][j] = W[1]

Con el límite de peso j, las selecciones óptimas entre los paquetes {1, 2,…, i – 1, i} para tener el mayor valor tendrán dos posibilidades:

  • Si no se selecciona el paquete i, B[i][j] es el valor máximo posible seleccionando entre los paquetes {1, 2,…, i – 1} con límite de peso de j. Tienes:
B[i][j] = B[i – 1][j]
  • Si se selecciona el paquete i (por supuesto, solo considere este caso cuando W[i] ≤ j), entonces B[i][j] es igual al valor V[i] del paquete i más el valor máximo que se puede obtener seleccionando entre paquetes {1, 2,…, i – 1} con límite de peso (j – W[i]). Es decir, en términos del valor que tienes:
B[i][j] = V[i] + B[i – 1][j – W[i]]

Debido a la creación de B[i][j], que es el valor máximo posible, B[i][j] será el máximo de los 2 valores anteriores.

Bases de la programación dinámica

Entonces, debes considerar si es mejor elegir el paquete i o no. A partir de ahí tienes la fórmula recursiva de la siguiente manera:

B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]

Es fácil ver B[0][j] = valor máximo posible seleccionando entre 0 paquete = 0.

Calcular la tabla de opciones

Usted construye una tabla de opciones basada en la fórmula recursiva anterior. Para comprobar si los resultados son correctos (si no son exactos, reconstruya la función objetivo B[i][j]). A través de la creación de la función objetivo B[i][j] y la tabla de opciones orientarás el calco.

La tabla de opciones B incluye n + 1 líneas, M + 1 columnas,

  • En primer lugar, se completa con la base de la programación dinámica: la línea 0 incluye todos los ceros.
  • Usando fórmulas recursivas, use la línea 0 para calcular la línea 1, use la línea 1 para calcular la línea 2, etc.… hasta que se calculen todas las líneas.
Calcular la tabla de opciones
Tabla de opciones

Trace

Al calcular la tabla de opciones te interesa B[n][M] que es el valor máximo que se obtiene al seleccionar en todos los n paquetes con límite de peso M.

  • If B[n][M] = B[n – 1][M] entonces el paquete n no está seleccionado, rastrea B[n – 1][M].
  • If B[n][M] ≠ B[n – 1][M], observa que la selección óptima tiene el paquete n y la traza B[n – 1][M – W[n]].

Continúe rastreando hasta llegar a la fila 0 de la tabla de opciones.

Algoritmo para consultar la tabla de opciones para encontrar los paquetes seleccionados

Nota: Si B[i][j] = B[i – 1][j], el paquete i no está seleccionado. B[n][W] es el valor total óptimo del paquete colocado en la mochila.

Pasos para el rastreo:

  • Paso 1: A partir de i = n, j = M.
  • Paso 2: Mire en la columna j, arriba desde abajo, encontrará la línea i tal que B[i][j] > B[i – 1][j]. Marcar el paquete seleccionado i: Seleccione [i] = verdadero;
  • Paso 3: j = B[i][j] – W[i]. Si j > 0, vaya al paso 2, otrowise ir al paso 4
  • Paso 4: Basado en la tabla de opciones para imprimir los paquetes seleccionados.

Código Java

public void knapsackDyProg(int W[], int V[], int M, int n) {
	int B[][] = new int[n + 1][M + 1];
	
	for (int i=0; i<=n; i++)
		for (int j=0; j<=M; j++) {
			B[i][j] = 0;
		}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= M; j++) {
			B[i][j] = B[i - 1][j];
			
			if ((j >= W[i-1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
				B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1]; 
			}
			
			System.out.print(B[i][j] + " ");
		}
		System.out.print("\n");
	}
	
	System.out.println("Max Value:\t" + B[n][M]);
	
	System.out.println("Selected Packs: ");
	
	while (n != 0) {
		if (B[n][M] != B[n - 1][M]) {
			System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
			
			M = M - W[n-1];
		}
		
		n--;
	}
}
Función mochilaDyProg() en Java

Función mochilaDyProg() en Java

Explicación del código de mochila:

  1. Cree la tabla B[][]. El valor predeterminado establecido para cada celda es 0.
  2. Construya la tabla B[][] de abajo hacia arriba. Calcula la tabla de opciones con la fórmula de recuperación.
  3. Calcule B[i][j]. Si no selecciona el paquete i.
  4. Luego evalúe: si selecciona el paquete i, será más beneficioso que restablecer B[i][j].
  5. Traza la tabla desde la fila n hasta la fila 0.
  6. Si eliges el paquete n. Una vez seleccionado el paquete n, solo puede agregar peso M – W[n – 1].


En este tutorial tienes dos ejemplos. Aquí hay código Java para ejecutar el programa anterior con dos ejemplos:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
	//int W[] = new int[]{3, 4, 5, 9, 4};
	int W[] = new int[]{12, 2, 1, 1, 4};
	
	//int V[] = new int[]{3, 4, 4, 10, 4};
	int V[] = new int[]{4, 2, 1, 2, 10};
	
	/*
	 * Max Weight
	 */
	//int M = 11;
	int M = 15;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackDyProg(W, V, M, n);
}

Tienes la salida:

  • Primer ejemplo:
0 0 0 3 3 3 3 3 3 3 3 3 
0 0 0 3 4 4 4 7 7 7 7 7 
0 0 0 3 4 4 4 7 7 8 8 8 
0 0 0 3 4 4 4 7 7 10 10 10 
0 0 0 3 4 4 4 7 8 10 10 11 
Max Value:	11
Selected Packs: 
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3
  • Segundo ejemplo:
0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6 
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7 
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs: 
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2