Saltar al contenido

Soluciones que utilizan el ejemplo de programación dinámica

¿Cuál es el problema de la mochila?

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

Aporte:

Producción:

El algoritmo Knapsack se puede dividir en dos tipos:

En este tutorial, aprenderá:

Breve introducción a la programación dinámica

En la estrategia de segmentación y conquista, divide el problema a resolver en subpuestos. Los subpuestos se dividen en subpuestos más pequeños. Esa tarea continuará hasta que encuentre subpublicaciones que se puedan resolver fácilmente. Sin embargo, en el proceso de compartir, a veces puede tener el mismo problema.

La idea básica de la programación dinámica de Knapsack es utilizar una tabla para almacenar las soluciones de los subproblemas resueltos. Si vuelve a enfrentarse al subempleo, solo tiene que crear la solución en la tabla sin volver a resolverla. Por tanto, los algoritmos diseñados por programación dinámica son muy eficientes.

Para resolver un problema a través de la programación dinámica, debe realizar las siguientes tareas:

Analizar el problema de la mochila 0/1

Al analizar el problema de la mochila 0/1 y usar programas dinámicos, puede obtener algunos puntos importantes. El valor del algoritmo de la 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, tiene 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á bidimensional.

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

Por ejemplo: B.[4][10] = 8. Esto significa que, en el mejor de los casos, el peso total de los paquetes seleccionados es 8, cuando hay 4 primeros paquetes para elegir (1 ° al 4 ° paquete) y el peso máximo de la mochila es 10. No es necesario. que los 4 elementos están seleccionados.

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

Entrada, usted define:

Donde solo hay 1 paquete para elegir. Calcula B.[1][j] para cada j: es decir, 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 mejores selecciones entre paquetes {1, 2, …, i – 1, i} tendrán dos posibilidades para tener el valor máximo:

B[i][j] = B[i – 1][j]
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] habrá un máximo de los 2 valores anteriores.

Base del programa dinámico

Entonces, debes pensar si es mejor elegir un paquete o no. A partir de ahí, tiene la fórmula recursiva de la siguiente manera:

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

B es fácil de ver[0][j] = valor máximo posible seleccionando entre 0 paquetes = 0.

Calcular la tabla de opciones

Construye una tabla de opciones basada en la fórmula recursiva anterior. Para comprobar si los resultados son correctos (si no exactamente, reconstruye la función del objetivo B.[i][j]). Creando una función objetivo B[i][j] y la tabla de opciones, guiarás el seguimiento.

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

Tabla de opciones

Rian

Al calcular la tabla de opciones, le interesa B.[n][M] que es el valor máximo obtenido al seleccionar en cada paquete n con el límite de peso M.

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

Algoritmo para ver la tabla de opciones para encontrar paquetes seleccionados

Nota: Si B.[i][j] = B.[i – 1][j], paquete no seleccionado i. B.[n][W] Es el valor total óptimo colocado en el paquete.

Pasos para el seguimiento:

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 KnapsackDyProg () en Java

Explicación del código de la mochila:

  1. Cree la tabla B.[][]. El valor predeterminado establecido para cada celda es 0.
  2. Tome la tabla B.[][] de forma ascendente. Calcule la tabla de opciones con la fórmula de recuperación.
  3. Calcular B.[i][j]. Si no selecciona un paquete en.
  4. Luego evalúe: si selecciona el paquete i, será más beneficioso que restablecer B[i][j].
  5. Trace la tabla desde la fila n hasta la fila 0.
  6. Si selecciona el paquete n. Cuando selecciona el paquete n, solo puede agregar el peso de M – W[n – 1].

En este tutorial, tiene dos ejemplos. Aquí está el código de 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:


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

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