Actualización: Lea acerca de cómo optimizar el espacio de la complejidad de la programación dinámica solución en mi artículo de seguimiento aquí.,
el problema de la mochila es un problema realmente interesante en combinatoria — para citar Wikipedia,
» dado un conjunto de elementos, cada uno con un peso y un valor, determine el número de cada elemento para incluir en una colección de modo que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible.»
de Wikipedia, vemos que hay algunas variaciones del problema de la mochila: 0-1 mochila, mochila limitada y mochila ilimitada., Hoy, nos centraremos en la variación más común( y más simple): el problema de la mochila 0-1.
un fraseo ligeramente más interesante y relacionable del problema de la mochila 0-1 es:
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 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. O lo toma o lo deja. Source
desafortunadamente, tuve algunas dificultades para entender algunas partes del artículo de Hackerearth, por lo que decidí escribir mi propio artículo. Este artículo se basará en gran medida en el artículo de Hackerearth y los fragmentos de código están escritos en Java. Voy a añadir explicaciones y elaboraciones adicionales donde creo que son necesarias.
vamos a resolver este problema con la programación dinámica., La programación dinámica requiere una subestructura óptima y sub-problemas superpuestos, los cuales están presentes en el problema de la mochila 0-1, como veremos.
está bien si no entiendes lo que son «subestructura óptima» y «sub-problemas superpuestos» (eso es un artículo para otro día). Esencialmente, solo significa un sabor particular de problemas que nos permiten reutilizar soluciones anteriores a problemas más pequeños para calcular una solución al problema actual. Verás lo que quiero decir en un rato.,
detalles del problema
dado que este es el problema de la mochila 0-1, podemos incluir un elemento en nuestra mochila o excluirlo, pero no incluir una fracción de él, o incluirlo varias veces.
solución
primero, creamos una matriz de 2 dimensiones (es decir, una tabla) de n + 1 filas y w + 1 columnas.
un número de fila I representa el conjunto de todos los elementos de las filas 1— i. por ejemplo, los valores de la fila 3 asumen que solo tenemos elementos 1, 2 y 3.
un número de columna J representa la capacidad de peso de nuestra mochila., Por lo tanto, los valores de la columna 5, por ejemplo, asumen que nuestra mochila puede contener 5 unidades de peso.
juntando todo, una entrada en la fila I, columna j representa el valor máximo que se puede obtener con los elementos 1, 2 , 3 i i, en una mochila que puede contener unidades de peso J.
llamemos a nuestra tabla mat para matrix. Por lo tanto, int mat = new int.
Paso 2:
podemos comenzar inmediatamente a rellenar algunas entradas en nuestra tabla: los casos base, para los que la solución es trivial., Por ejemplo, en la fila 0, cuando no tenemos elementos para elegir, el valor máximo que se puede almacenar en cualquier mochila debe ser 0. Del mismo modo, en la columna 0, para una mochila que puede contener 0 unidades de peso, el valor máximo que se puede almacenar en ella es 0. (Estamos asumiendo que no hay objetos valiosos sin masa.)
podemos hacer esto con 2 bucles for:
Paso 3 (el quid de la cuestión):
Ahora, queremos empezar a llenar nuestra mesa., Al igual que con todas las soluciones de programación dinámica, en cada paso, haremos uso de nuestras soluciones a sub-problemas anteriores.
primero describiré la lógica, antes de mostrar un ejemplo concreto.
la relación entre el valor en la fila I, columna j y los valores con los subproblemas anteriores es la siguiente:
recuerde que en la fila I y la columna j, estamos abordando un subproblema que consiste en los ítems 1, 2, 3 i i con una mochila de capacidad J. Hay 2 opciones en este punto: podemos incluir el elemento i o no., Por lo tanto, necesitamos comparar el valor máximo que podemos obtener con y sin item i.
el valor máximo que podemos obtener sin item I se puede encontrar en la fila i-1, columna j. esta parte es fácil. El razonamiento es sencillo: cualquier valor máximo que podamos obtener con los ítems 1, 2, 3 obviously obviamente debo ser el mismo valor máximo que podemos obtener con los ítems 1, 2, 3 i i – 1, si elegimos no incluir el ítem i.
para calcular el valor máximo que podemos obtener con el ítem i, primero necesitamos comparar el peso del ítem I con la capacidad de peso de la mochila., Obviamente, si el artículo i pesa más de lo que la mochila puede contener, no podemos incluirlo, por lo que no tiene sentido realizar el cálculo. En ese caso, la solución a este problema es simplemente el valor máximo que podemos obtener sin el elemento i (es decir, el valor en la fila anterior, en la misma columna).
sin embargo, supongamos que el objeto I pesa menos que la capacidad de la mochila. Por lo tanto, tenemos la opción de incluirlo, si potencialmente aumenta el valor máximo obtenible., El valor máximo que se puede obtener al incluir el elemento i es, por lo tanto, = el valor del elemento i en sí + el valor máximo que se puede obtener con la capacidad restante de la mochila. Evidentemente, queremos aprovechar al máximo la capacidad de nuestra mochila y no desperdiciar ninguna de las capacidades restantes.
Por lo tanto, en la fila I y la columna j (que representa el valor máximo que podemos obtener allí), elegiríamos el valor máximo que podemos obtener sin el elemento i, o el valor máximo que podemos obtener con el elemento i, el que sea mayor.
Aquí hay un ejemplo concreto de lo que quiero decir.,
En la fila 3 (punto 2), y la columna 5 (mochila de capacidad de 4), podemos escoger para incluir el punto 2 (que pesa 4 unidades) o no. Si elegimos no incluirlo, el valor máximo que podemos obtener es el mismo que si solo tenemos el elemento 1 para elegir (que se encuentra en la fila anterior, es decir, 0)., Si queremos incluir el ítem 2, el valor máximo que podemos obtener con el ítem 2 es el valor del ítem 2 (40) + el valor máximo que podemos obtener con la capacidad restante (que es 0, porque la mochila ya está completamente llena).
en la fila 3 (Elemento 2) y la columna 10 (Capacidad de mochila de 9), nuevamente, podemos elegir incluir el elemento 2 o no. Si elegimos no hacerlo, el valor máximo que podemos obtener es el mismo que en la fila anterior en la misma columna, es decir, 10 (incluyendo solo el elemento 1, que tiene un valor de 10). Si incluimos el ítem 2, tenemos una capacidad restante de mochila de 9-4 = 5., Podemos encontrar el valor máximo que se puede obtener con una capacidad de 5 mirando la fila de arriba, en la columna 5. Por lo tanto, el valor máximo que podemos obtener al incluir el elemento 2 es 40 (el valor del elemento 2) + 10 = 50.
elegimos el mayor de 50 vs 10, por lo que el valor máximo que podemos obtener con los artículos 1 y 2, con una capacidad de mochila de 9, es 50.,
el algoritmo se puede expresar en Java de la siguiente manera:
Paso 4 (Solución final):
una vez que la tabla se ha rellenado, la solución final se puede encontrar en la última fila de la representa el valor máximo que se puede obtener con todos los artículos y la capacidad total de la mochila.
return mat;
código de trabajo:
Nota: aquí, imprimí la respuesta final en lugar de devolverla, ya que todo está alojado en public static void main.,
Thanks for reading!