Aquí la mochila es como un contenedor o una bolsa. Supongamos que hemos dado algunos elementos que tienen algunos pesos o beneficios. Tenemos que poner algunos artículos en la mochila de tal manera que el valor total produzca el máximo beneficio.

Por ejemplo, el peso del contenedor es de 20 kg. Tenemos que seleccionar los artículos de tal manera que la suma del peso de los artículos sea menor o igual al peso del contenedor, y la ganancia sea máxima.

Hay dos tipos de problemas de mochila:

• 0/1 problema de mochila
• Problema de mochila fraccionaria

Discutiremos ambos problemas uno por uno. Primero, aprenderemos sobre el problema de la mochila 0/1.

¿Cuál es el problema de la mochila 0/1?

El problema de la mochila 0/1 significa que los artículos están completamente llenos o no hay ningún artículo en una mochila. Por ejemplo, tenemos dos artículos que pesan 2 kg y 3 kg, respectivamente. Si elegimos el artículo de 2 kg, entonces no podemos seleccionar el artículo de 1 kg del artículo de 2 kg (el artículo no es divisible); Tenemos que recoger el artículo de 2 kg por completo. Este es un problema de mochila 0/1 en el que seleccionamos el artículo por completo o seleccionamos ese artículo. El problema de la mochila 0/1 se resuelve mediante programación dinámica.

¿Qué es el problema de la mochila fraccionaria?

El problema de la mochila fraccionaria significa que podemos dividir el artículo. Por ejemplo, tenemos un artículo de 3 kg, entonces podemos elegir el artículo de 2 kg y dejar el artículo de 1 kg. El problema de la mochila fraccionaria se resuelve mediante el enfoque Greedy.

Ejemplo de problema de mochila 0/1.

Considere el problema que tiene pesos y beneficios:

Pesos: {3, 4, 6, 5}

Beneficios: {2, 3, 1, 4}

El peso de la mochila es de 8 kg.

El número de artículos es 4.

El problema anterior se puede resolver utilizando el siguiente método:

X_i= {1, 0, 0, 1}

= {0, 0, 0, 1}

desventajas de la banca en línea

= {0, 1, 0, 1}

Las anteriores son las posibles combinaciones. 1 indica que el artículo se ha seleccionado por completo y 0 significa que no se ha seleccionado ningún artículo. Dado que hay 4 elementos, las posibles combinaciones serán:

2⁴= 16; Entonces. Hay 16 combinaciones posibles que se pueden hacer usando el problema anterior. Una vez realizadas todas las combinaciones, tenemos que seleccionar la combinación que proporcione el máximo beneficio.

Otro enfoque para resolver el problema es el enfoque de programación dinámica. En el enfoque de programación dinámica, el problema complicado se divide en subproblemas, luego encontramos la solución de un subproblema y la solución del subproblema se utilizará para encontrar la solución de un problema complejo.

¿Cómo se puede resolver este problema utilizando el enfoque de programación dinámica?

Primero,

Creamos una matriz que se muestra a continuación:

En la matriz anterior, las columnas representan el peso, es decir, 8. Las filas representan las ganancias y el peso de los artículos. Aquí no hemos tomado el peso 8 directamente, el problema se divide en subproblemas, es decir, 0, 1, 2, 3, 4, 5, 6, 7, 8. La solución de los subproblemas se guardaría en el Las celdas y la respuesta al problema se almacenarían en la celda final. Primero, escribimos los pesos en orden ascendente y las ganancias según sus pesos, como se muestra a continuación:

En_i= {3, 4, 5, 6}

pag_i= {2, 3, 4, 1}

La primera fila y la primera columna serían 0 ya que no hay ningún elemento para w=0

Cuando i=1, W=1

En₁= 3; Dado que solo tenemos un artículo en el conjunto que pesa 3, pero la capacidad de la mochila es 1. No podemos llenar el artículo de 3 kg en la mochila con capacidad de 1 kg, así que agregue 0 en M[1][1] como se muestra a continuación. :

Cuando i = 1, W = 2

En₁= 3; Dado que solo tenemos un artículo en el conjunto que pesa 3, pero la capacidad de la mochila es 2. No podemos llenar el artículo de 3 kg en la mochila con capacidad de 2 kg, así que agregue 0 en M[1][2] como se muestra a continuación. :

Cuando i=1, W=3

En₁= 3; Dado que solo tenemos un artículo en el conjunto que tiene un peso igual a 3, y el peso de la mochila también es 3; por lo tanto, podemos llenar la mochila con un artículo de peso igual a 3. Ponemos la ganancia correspondiente al peso 3, es decir, 2 en M[1][3] como se muestra a continuación:

Cuando i=1, W = 4

_W1= 3; Dado que solo tenemos un artículo en el conjunto que tiene un peso igual a 3 y el peso de la mochila es 4; por lo tanto, podemos llenar la mochila con un artículo de peso igual a 3. Ponemos la ganancia correspondiente al peso 3, es decir, 2 en M[1][4] como se muestra a continuación:

Cuando i=1, W = 5

_W1= 3; Dado que solo tenemos un artículo en el conjunto que tiene un peso igual a 3 y el peso de la mochila es 5; por lo tanto, podemos llenar la mochila con un artículo de peso igual a 3. Ponemos la ganancia correspondiente al peso 3, es decir, 2 en M[1][5] como se muestra a continuación:

Cuando i = 1, W = 6

_W1= 3; Dado que solo tenemos un artículo en el conjunto que tiene un peso igual a 3 y el peso de la mochila es 6; por lo tanto, podemos llenar la mochila con un artículo de peso igual a 3. Ponemos la ganancia correspondiente al peso 3, es decir, 2 en M[1][6] como se muestra a continuación:

Cuando i=1, W = 7

_W1= 3; Dado que solo tenemos un artículo en el conjunto que tiene un peso igual a 3 y el peso de la mochila es 7; por lo tanto, podemos llenar la mochila con un artículo de peso igual a 3. Ponemos la ganancia correspondiente al peso 3, es decir, 2 en M[1][7] como se muestra a continuación:

Cuando i = 1, W = 8

_W1= 3; Dado que solo tenemos un artículo en el conjunto que tiene un peso igual a 3 y el peso de la mochila es 8; por lo tanto, podemos llenar la mochila con un artículo de peso igual a 3. Ponemos la ganancia correspondiente al peso 3, es decir, 2 en M[1][8] como se muestra a continuación:

Ahora el valor de 'i' se incrementa y se convierte en 2.

Cuando i = 2, W = 1

El peso correspondiente al valor 2 es 4, es decir, w₂= 4. Dado que solo tenemos un artículo en el conjunto que tiene un peso igual a 4, y el peso de la mochila es 1. No podemos poner el artículo de peso 4 en una mochila, por lo que sumamos 0 en M[2][1 ] se muestra a continuación:

Cuando i = 2, W = 2

El peso correspondiente al valor 2 es 4, es decir, w₂= 4. Dado que solo tenemos un artículo en el conjunto que tiene un peso igual a 4, y el peso de la mochila es 2. No podemos poner el artículo de peso 4 en una mochila, por lo que sumamos 0 en M[2][2 ] se muestra a continuación:

Cuando i = 2, W = 3

El peso correspondiente al valor 2 es 4, es decir, w₂= 4. Dado que tenemos dos artículos en el conjunto que tienen pesos 3 y 4, y el peso de la mochila es 3. Podemos poner el artículo de peso 3 en una mochila, entonces sumamos 2 en M[2][3] se muestra a continuación:

Cuando i = 2, W = 4

El peso correspondiente al valor 2 es 4, es decir, w₂= 4. Dado que tenemos dos artículos en el conjunto que tienen pesos 3 y 4, y el peso de la mochila es 4. Podemos poner el artículo de peso 4 en una mochila ya que la ganancia correspondiente al peso 4 es mayor que la del artículo que tiene peso. 3, entonces sumamos 3 en M[2][4] como se muestra a continuación:

Cuando i = 2, W = 5

El peso correspondiente al valor 2 es 4, es decir, w₂= 4. Como tenemos dos artículos en el conjunto que tienen pesos 3 y 4, y el peso de la mochila es 5. Podemos poner el artículo de peso 4 en una mochila y la ganancia correspondiente al peso es 3, entonces sumamos 3 en M[2][5] se muestra a continuación:

Cuando i = 2, W = 6

El peso correspondiente al valor 2 es 4, es decir, w₂= 4. Como tenemos dos artículos en el conjunto que tienen pesos 3 y 4, y el peso de la mochila es 6. Podemos poner el artículo de peso 4 en una mochila y la ganancia correspondiente al peso es 3, entonces sumamos 3 en M[2][6] se muestra a continuación:

Cuando i = 2, W = 7

El peso correspondiente al valor 2 es 4, es decir, w₂= 4. Como tenemos dos artículos en el conjunto que tienen pesos 3 y 4, y el peso de la mochila es 7. Podemos poner artículos de peso 4 y 3 en una mochila y las ganancias correspondientes a los pesos son 2 y 3; por lo tanto, la ganancia total es 5, por lo que sumamos 5 en M[2][7] como se muestra a continuación:

Cuando i = 2, W = 8

El peso correspondiente al valor 2 es 4, es decir, w₂= 4. Como tenemos dos artículos en el conjunto que tienen pesos 3 y 4, y el peso de la mochila es 7. Podemos poner artículos de peso 4 y 3 en una mochila y las ganancias correspondientes a los pesos son 2 y 3; por lo tanto, la ganancia total es 5, por lo que sumamos 5 en M[2][7] como se muestra a continuación:

Ahora el valor de 'i' se incrementa y se convierte en 3.

Cuando i = 3, W = 1

descargar turbo c++

El peso correspondiente al valor 3 es 5, es decir, w₃= 5. Como tenemos tres artículos en el conjunto que tienen pesos 3, 4 y 5, y el peso de la mochila es 1. No podemos poner ninguno de los artículos en una mochila, entonces sumamos 0 en M[3][ 1] se muestra a continuación:

Cuando i = 3, W = 2

El peso correspondiente al valor 3 es 5, es decir, w₃= 5. Dado que tenemos tres artículos en el conjunto que pesan 3, 4 y 5, y el peso de la mochila es 1. No podemos poner ninguno de los artículos en una mochila, por lo que sumamos 0 en M[3][ 2] se muestra a continuación:

Cuando i = 3, W = 3

El peso correspondiente al valor 3 es 5, es decir, w₃= 5. Dado que tenemos tres artículos en el conjunto de peso 3, 4 y 5 respectivamente y el peso de la mochila es 3. El artículo con un peso 3 se puede poner en la mochila y la ganancia correspondiente al artículo es 2, entonces sumamos 2 en M[3][3] como se muestra a continuación:

Cuando i = 3, W = 4

El peso correspondiente al valor 3 es 5, es decir, w₃= 5. Dado que tenemos tres artículos en el conjunto de peso 3, 4 y 5 respectivamente, y el peso de la mochila es 4. Podemos quedarnos con el artículo de peso 3 o 4; la ganancia (3) correspondiente al peso 4 es mayor que la ganancia correspondiente al peso 3, por lo que sumamos 3 en M[3][4] como se muestra a continuación:

Cuando i = 3, W = 5

El peso correspondiente al valor 3 es 5, es decir, w₃= 5. Dado que tenemos tres artículos en el conjunto de peso 3, 4 y 5 respectivamente, y el peso de la mochila es 5. Podemos quedarnos con el artículo de peso 3, 4 o 5; la ganancia (3) correspondiente al peso 4 es mayor que la ganancia correspondiente al peso 3 y 5, por lo que sumamos 3 en M[3][5] como se muestra a continuación:

Cuando i = 3, W = 6

El peso correspondiente al valor 3 es 5, es decir, w₃= 5. Dado que tenemos tres artículos en el conjunto de peso 3, 4 y 5 respectivamente, y el peso de la mochila es 6. Podemos quedarnos con el artículo de peso 3, 4 o 5; la ganancia (3) correspondiente al peso 4 es mayor que la ganancia correspondiente al peso 3 y 5, por lo que sumamos 3 en M[3][6] como se muestra a continuación:

Cuando i = 3, W = 7

El peso correspondiente al valor 3 es 5, es decir, w₃= 5. Como tenemos tres artículos en el conjunto de peso 3, 4 y 5 respectivamente, y el peso de la mochila es 7. En este caso, podemos quedarnos con los artículos de peso 3 y 4, la suma de la ganancia sería igual a (2 + 3), es decir, 5, por lo que sumamos 5 en M[3][7] como se muestra a continuación:

Cuando i = 3, W = 8

El peso correspondiente al valor 3 es 5, es decir, w₃= 5. Como tenemos tres artículos en el conjunto de peso 3, 4 y 5 respectivamente, y el peso de la mochila es 8. En este caso, podemos quedarnos con los artículos de peso 3 y 4, la suma de los la ganancia sería igual a (2 + 3), es decir, 5, por lo que sumamos 5 en M[3][8] como se muestra a continuación:

Ahora el valor de 'i' se incrementa y se convierte en 4.

Cuando i = 4, W = 1

El peso correspondiente al valor 4 es 6, es decir, w₄= 6. Como tenemos cuatro artículos en el conjunto de pesos 3, 4, 5 y 6 respectivamente, y el peso de la mochila es 1. El peso de todos los artículos es mayor que el peso de la mochila, por lo que no podemos añadir cualquier artículo en la mochila; Por lo tanto, sumamos 0 en M[4][1] como se muestra a continuación:

Cuando i = 4, W = 2

El peso correspondiente al valor 4 es 6, es decir, w₄= 6. Como tenemos cuatro artículos en el conjunto de pesos 3, 4, 5 y 6 respectivamente, y el peso de la mochila es 2. El peso de todos los artículos es mayor que el peso de la mochila, por lo que no podemos añadir cualquier artículo en la mochila; Por lo tanto, sumamos 0 en M[4][2] como se muestra a continuación:

Cuando i = 4, W = 3

El peso correspondiente al valor 4 es 6, es decir, w₄= 6. Como tenemos cuatro artículos en el conjunto de pesos 3, 4, 5 y 6 respectivamente, y el peso de la mochila es 3. El artículo con peso 3 se puede poner en la mochila y la ganancia correspondiente al El peso 4 es 2, por lo que agregaremos 2 en M[4][3] como se muestra a continuación:

Cuando i = 4, W = 4

El peso correspondiente al valor 4 es 6, es decir, w₄= 6. Como tenemos cuatro artículos en el conjunto de pesos 3, 4, 5 y 6 respectivamente, y el peso de la mochila es 4. El artículo con peso 4 se puede poner en la mochila y la ganancia correspondiente al El peso 4 es 3, por lo que agregaremos 3 en M[4][4] como se muestra a continuación:

Cuando i = 4, W = 5

El peso correspondiente al valor 4 es 6, es decir, w₄= 6. Como tenemos cuatro artículos en el conjunto de pesos 3, 4, 5 y 6 respectivamente, y el peso de la mochila es 5. El artículo con peso 4 se puede poner en la mochila y la ganancia correspondiente al El peso 4 es 3, por lo que agregaremos 3 en M[4][5] como se muestra a continuación:

Cuando i = 4, W = 6

El peso correspondiente al valor 4 es 6, es decir, w₄= 6. Dado que tenemos cuatro artículos en el conjunto de pesos 3, 4, 5 y 6 respectivamente, y el peso de la mochila es 6. En este caso, podemos poner los artículos en la mochila de peso 3, 4 , 5 o 6 pero el beneficio, es decir, 4 correspondiente al peso 6 es el mayor entre todos los artículos; por lo tanto, sumamos 4 en M[4][6] como se muestra a continuación:

Cuando i = 4, W = 7

El peso correspondiente al valor 4 es 6, es decir, w₄= 6. Dado que tenemos cuatro artículos en el conjunto de pesos 3, 4, 5 y 6 respectivamente, y el peso de la mochila es 7. Aquí, si sumamos dos artículos con pesos 3 y 4, produciremos el máximo beneficio, es decir, (2 + 3) es igual a 5, por lo que sumamos 5 en M[4][7] como se muestra a continuación:

Cuando i = 4, W = 8

El peso correspondiente al valor 4 es 6, es decir, w₄= 6. Dado que tenemos cuatro artículos en el conjunto de pesos 3, 4, 5 y 6 respectivamente, y el peso de la mochila es 8. Aquí, si sumamos dos artículos con pesos 3 y 4, produciremos el máximo beneficio, es decir, (2 + 3) es igual a 5, por lo que sumamos 5 en M[4][8] como se muestra a continuación:

Como podemos observar en la tabla anterior, 5 es el beneficio máximo entre todas las entradas. El puntero apunta a la última fila y a la última columna que tiene 5 valores. Ahora compararemos el valor 5 con la fila anterior; si la fila anterior, es decir, i = 3, contiene el mismo valor 5, entonces el puntero se desplazará hacia arriba. Dado que la fila anterior contiene el valor 5, el puntero se desplazará hacia arriba como se muestra en la siguiente tabla:

Nuevamente, compararemos el valor 5 de la fila anterior, es decir, i = 2. Dado que la fila anterior contiene el valor 5, el puntero nuevamente se desplazará hacia arriba como se muestra en la siguiente tabla:

Nuevamente, compararemos el valor 5 de la fila anterior, es decir, i = 1. Dado que la fila anterior no contiene el mismo valor, consideraremos la fila i = 1, y el peso correspondiente a la fila es 4. Por lo tanto , hemos seleccionado el peso 4 y hemos rechazado los pesos 5 y 6 que se muestran a continuación:

x = {1, 0, 0}

La ganancia correspondiente al peso es 3. Por lo tanto, la ganancia restante es (5 - 3) igual a 2. Ahora compararemos este valor 2 con la fila i = 2. Ya que la fila (i = 1) contiene el valor 2 ; por lo tanto, el puntero se desplazó hacia arriba como se muestra a continuación:

Nuevamente comparamos el valor 2 con una fila anterior, es decir, i = 1. Dado que la fila i = 0 no contiene el valor 2, se seleccionará la fila i = 1 y se mostrará el peso correspondiente a i = 1. abajo:

X = {1, 1, 0, 0}

cadena de java

El beneficio correspondiente al peso es 2. Por lo tanto, el beneficio restante es 0. Comparamos el valor 0 con la fila anterior. Dado que la fila anterior contiene un valor 0 pero la ganancia correspondiente a esta fila es 0. En este problema, se seleccionan dos pesos, es decir, 3 y 4 para maximizar la ganancia.