El problema de la Mochila
he encontrado la Mochila problema difícil e interesante al mismo tiempo. Estoy seguro de que si está visitando esta página, ya conoce la declaración del problema, pero solo para completar:
problema:
dada una mochila de una capacidad máxima de W Y N artículos, cada uno con su propio valor y peso, agregue artículos dentro de la mochila de modo que el Contenido final tenga el valor máximo. ¡Caramba !!,
Esta es la forma general en que se explica el problema: considere que un ladrón entra en una casa para robar y lleva una mochila. Hay un número fijo de artículos en el hogar – cada uno con su propio peso y valor – joyas, con menos peso y valor más alto vs tablas, con menos valor pero mucho más pesado. Para añadir combustible al fuego, el ladrón tiene una mochila vieja que tiene capacidad limitada. Obviamente, no puede dividir la mesa por la mitad o las joyas en 3/4., Lo toma o lo deja
ejemplo :
Knapsack Max weight : W = 10 (units)Total items : N = 4Values of items : v = {10, 40, 30, 50}Weight of items : w = {5, 4, 6, 3}
Una mirada superficial a los datos de ejemplo nos dice que el valor máximo que podríamos acomodar con el límite de peso máximo de 10 es 50 + 40 = 90 con un peso de 7.
enfoque:
la forma en que esto se resuelve de manera óptima es utilizando la solución de programación dinámica para conjuntos más pequeños de problemas de mochila y luego expandirlos para el problema más grande.,
construyamos una matriz de peso de elemento X llamada V (matriz de valores):
V = 4 rows * 10 columnscada uno de los valores en esta matriz representan un problema de mochila más pequeño.
caso Base 1: tomemos el caso de la 0A columna. Solo significa que la mochila tiene 0 capacidad. ¿Qué puedes guardar en ellos? Nada. Por lo tanto, vamos a llenarlos todos con 0s.
caso Base 2 : tomemos el caso de la fila 0. Solo significa que no hay artículos en la casa. ¿Qué tienes en la mochila si no hay objetos? ¡Nada otra vez !!! Todos ceros.,
Solución:
1) Ahora, vamos a empezar a llenar la matriz de fila. ¿Qué significan la fila 1 y la columna 1? Que dado el primer elemento (fila), se puede acomodar en la mochila con capacidad 1 (columna). No. El peso del primer artículo es 5. Por lo tanto, vamos a llenar 0. De hecho, no podríamos rellenar nada hasta llegar a la columna 5 (peso 5).
2) Una vez que llegamos a la columna 5 (que representa el peso 5) en la primera fila, significa que podríamos acomodar el elemento 1., Vamos a llenar 10 allí (recuerde, esto es una matriz de valores):
3) pasando, para el peso 6 (columna 6), podemos acomodar cualquier otra cosa con el peso restante de 1 (peso – peso de este elemento => 6 – 5). Oye, recuerda, estamos en el primer tema. Por lo tanto, es algo intuitivo que el resto de la fila será el mismo valor también, ya que no podemos agregar ningún otro artículo para ese peso extra que tenemos.,
4) por lo tanto, lo siguiente interesante sucede cuando llegamos a la columna 4 en la tercera fila. El peso corriente actual es 4.
debemos comprobar los siguientes casos.
1) podemos acomodar el artículo 2-Sí, podemos. El peso del artículo 2 es 4.
2) ¿El valor para el peso actual es mayor sin el ítem 2? – Compruebe la fila anterior para el mismo peso. No. la fila anterior * tiene 0 en ella, ya que no pudimos acomodar el artículo 1 en peso 4.
3) ¿Podemos acomodar dos artículos en el mismo peso para que podamos maximizar el valor? – No., El peso restante después de deducir el peso del Artículo 2 es 0.
¿por Qué la fila anterior?
simplemente porque la fila anterior en peso 4 en sí es una solución de mochila más pequeña que da el valor máximo que podría acumularse para ese peso hasta ese punto (atravesando los artículos).,
ejemplificando,
1) el valor del ítem actual = 40
2) el peso del ítem actual = 4
3) el peso que queda = 4 – 4 = 0
4) Compruebe la fila anterior (el ítem anterior en el caso del ítem 1 o el valor máximo acumulado en el caso del resto de las filas). Para el peso restante 0, ¿podemos acomodar el artículo 1? En pocas palabras, ¿hay algún valor en la fila anterior para el peso dado?,
El cálculo va así :
1) Tome el valor máximo para el mismo peso, sin este elemento:
previous row, same weight = 0=> V2) Tomar el valor del elemento actual + valor que podríamos acomodar con el peso restante:
Max entre los dos es de 40 (0 y 40).
3) el siguiente y el evento más importante ocurre en la columna 9 y la fila 2. Lo que significa que tenemos un peso de 9 y tenemos dos artículos. Mirando los datos de ejemplo podríamos acomodar los dos primeros elementos., Aquí, tenemos en cuenta algunas cosas:
- El valor del elemento actual = 40
- El peso del elemento actual = 4
- El peso que sobra = 9 – 4 = 5
- Verificación de la fila de arriba. En el peso restante 5, somos capaces de acomodar el artículo 1.
Así, el cálculo es el siguiente :
1) Tome el valor máximo para el mismo peso, sin este elemento:
previous row, same weight = 102) Tomar el valor del elemento actual + valor que se puede acumular con el resto de peso:
Value of current item (40)+ value in previous row with weight 5 (total weight until now (9) - weight of the current item (4))= 1010 vs 50 = 50.,
al final de resolver todos estos problemas más pequeños, solo tenemos que devolver el valor en V – Item 4 en el peso 10:
Complexity
analizar la complejidad de la solución es bastante sencillo. Solo tenemos un bucle para W dentro de un bucle de N => o (NW)
implementación:
Aquí viene el código de implementación obligatorio en Java: