¿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:
- Peso máximo M y número de bultos n.
- Serie de pesos W.[i] y el valor correspondiente de V.[i].
Producción:
- Maximice el valor y el peso correspondiente en capacidad.
- Qué paquetes se llevará el ladrón.
El algoritmo Knapsack se puede dividir en dos tipos:
- Problema 0/1 Mochila con programación dinámica. En este tipo de algoritmo Knapsack, todos los paquetes se pueden construir o no. Además, el ladrón no puede tomar una fracción de un paquete integrado o tomar un paquete más de una vez. Este tipo se puede resolver mediante un enfoque de registro dinámico.
- Mochila Algoritmo de problema fraccional. Este tipo se puede resolver con Greedy Strategy.
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:
- Encuentre soluciones a los subproblemas más pequeños.
- Descubra la fórmula (o regla) para construir una solución de subtrabajos a través de soluciones de los subtrabajos más pequeños.
- Cree una tabla que almacene soluciones de correo electrónico secundario. Luego calcule la solución del subproblema según la fórmula encontrada y guárdela en la tabla.
- A partir de los subproblemas resueltos, encontrará la solución del problema original.
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:
- Cuántos paquetes se están considerando
- 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:
- la función objetivo dependerá de dos cantidades variables
- 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.
- B es el valor máximo cuando se selecciona en paquetes con el límite de peso M[n][M]. En otras palabras: cuando los paquetes están en proceso de selección, B.[i][j] el peso óptimo cuando j es el peso máximo de la mochila.
- El peso óptimo es siempre menor o igual que el peso máximo: B.[i][j] ≤ 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:
- W.[i], V.[i] a su vez, el peso y el valor de un paquete de i, que contiene i {1,…, n}.
- M es el peso máximo que puede llevar la mochila.
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:
- Si no se selecciona el paquete i, B.[i][j] el valor máximo posible seleccionando paquetes {1, 2, …, i – 1} con un límite de peso de j. Tu tienes _:
B[i][j] = B[i – 1][j]
- Si se selecciona un paquete en (por supuesto, considere este caso solo cuando W sea.[i] ≤ j) luego B.[i][j] igual al valor de V.[i] paquete i más el valor máximo se puede obtener seleccionando paquetes {1, 2, …, i – 1} con un límite de peso (j – W[i]). Es decir, en términos de su valor:
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,
- Primero, lleno de los conceptos básicos de los programas dinámicos: 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.
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.
- Ambas cosas B.[n][M] = B.[n – 1][M] entonces el paquete n no está seleccionado, rastrea B[n – 1][M].
- Ambas cosas B.[n][M] ≠ B.[n – 1][M], observa que el paquete ny la pista B son la mejor opción[n – 1][M – W[n]].
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:
- Paso 1: A partir de i = n, j = M.
- Paso 2: Mire en la columna j, arriba desde abajo, encuentre la línea i de modo que B.[i][j] > B.[i – 1][j]. Marcar el paquete seleccionado en: Seleccionar [i] cierto;
- Paso 3: j = B.[i][j] – W.[i]. Si j> 0, vaya al paso 2 o 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--;
}
}
Explicación del código de la mochila:
- Cree la tabla B.[][]. El valor predeterminado establecido para cada celda es 0.
- Tome la tabla B.[][] de forma ascendente. Calcule la tabla de opciones con la fórmula de recuperación.
- Calcular B.[i][j]. Si no selecciona un paquete en.
- Luego evalúe: si selecciona el paquete i, será más beneficioso que restablecer B[i][j].
- Trace la tabla desde la fila n hasta la fila 0.
- 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