dynamic-programming
Problema de mochila

Observaciones

0-1 Problema de mochila

Supongamos que se le pregunta, dado el peso total que puede llevar en su mochila y algunos artículos con su peso y valores, ¿cómo puede tomar esos artículos de tal manera que la suma de sus valores sea máxima, pero la suma de sus pesos no no exceder el peso total que puede llevar? El 0-1 indica que eliges el ítem o no. También tenemos una cantidad de cada artículo. Significa que, no se puede dividir el elemento. Si no fue un problema de mochila 0-1 , eso significa que si pudo dividir los artículos, hay una solución codiciosa, que se llama problema de mochila fraccional .

Por ahora, concentrémonos en nuestro problema actual. Por ejemplo, digamos que tenemos una capacidad de mochila de 7 . Tenemos 4 artículos. Sus pesos y valores son:

+----------+---+---+---+---+
|   Item   | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
|  Weight  | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
|   Value  | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+

Un método de fuerza bruta sería tomar todas las combinaciones posibles de elementos. Luego, podemos calcular sus pesos totales y excluirlos que excedan la capacidad de nuestra mochila y descubrir el que nos da el máximo valor. Para 4 artículos, tendremos que verificar ( 4! - 1 ) = 23 combinaciones posibles (excluyendo una sin artículos). Esto es bastante engorroso cuando aumenta la cantidad de elementos. Aquí, algunos aspectos que podemos notar, es decir:

• Podemos tomar ítems menores y calcular el valor máximo que podemos obtener con esos ítems y combinarlos. Entonces nuestro problema se puede dividir en subproblemas.
• Si calculamos las combinaciones para el elemento {1,2} , podemos usarlo cuando calculamos {1, 2, 3} .
• Si minimizamos el peso y maximizamos el valor, podemos encontrar nuestra solución óptima.

Por estas razones, usaremos la programación dinámica para resolver nuestro problema. Nuestra estrategia será: cada vez que llegue un nuevo artículo, verificaremos si podemos elegir el artículo o no, y nuevamente seleccionaremos los artículos que nos dan el máximo valor. Ahora, si seleccionamos el artículo, nuestro valor será el valor del artículo, más el valor que podamos obtener al restar el valor de nuestra capacidad y el máximo que podemos obtener para el peso restante. Si no seleccionamos el artículo, seleccionaremos los artículos que nos den el valor máximo sin incluir el artículo. Intentemos entenderlo con nuestro ejemplo:

Tomaremos una tabla de matriz 2D, donde el número de columnas será el valor máximo que podemos obtener al tomar los elementos + 1. Y el número de filas será el mismo que el número de elementos. Nuestra matriz se verá como:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

Hemos incorporado el peso y el valor de cada elemento a la matriz para nuestra conveniencia. Recuerde que estos no son parte de la matriz, son solo para fines de cálculo, no necesita almacenar estos valores en la matriz de tabla .

Nuestra primera columna está llena de 0 . Significa que si nuestra capacidad máxima es 0 , sin importar el artículo que tengamos, ya que no podemos elegir ningún artículo, nuestro valor máximo será 0 . Empecemos por la tabla [0] [1] . Cuando llenamos la Tabla [1] [1] , nos preguntamos si nuestra capacidad máxima era 1 y solo teníamos el primer elemento, ¿cuál sería nuestro valor máximo? Lo mejor que podemos hacer es 1 , eligiendo el artículo. Para la Tabla [0] [2] eso significa que si nuestra capacidad máxima es 2 y solo tenemos el primer elemento, el valor máximo que podemos obtener es 1 . Esto será igual para la Tabla [0] [3] , la Tabla [0] [4] , la Tabla [0] [5] , la Tabla [0] [6] y la Tabla [0] [7] . Esto se debe a que solo tenemos un elemento, lo que nos da valor 1 . Como solo tenemos 1 cantidad de cada artículo, no importa cómo aumentemos la capacidad de nuestra mochila, de un artículo, 1 es el mejor valor que podemos obtener. Así que nuestra matriz se verá como:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

Continuando, para la Tabla [1] [1] , nos preguntamos si teníamos los ítems 1 y 2 y si la capacidad máxima de nuestra mochila era 1 , ¿cuál es el valor máximo que podemos obtener? Si tomamos los ítems 1 y 2 , el peso total será 4 , lo que excederá nuestra capacidad de mochila actual. Así que el artículo 2 no puede ser seleccionado. Ahora, ¿qué es lo mejor que podemos hacer sin tomar el artículo 2 ? El valor de la parte superior, que es la Tabla [0] [1], que contiene el valor máximo que podemos obtener si tuviéramos la capacidad máxima 1 y no seleccionáramos el segundo elemento. Para la Tabla [1] [2] , dado que 2 es menor que el peso [2] , que es el peso del segundo artículo, no podemos tomar el artículo. Así que podemos establecer que, si el peso del artículo actual es mayor que nuestra capacidad máxima, no podemos tomar ese artículo. En este caso, simplemente tomaremos el valor de arriba, que representa el valor máximo que podemos tomar excluyendo el artículo.

if weight[i] > j
    Table[i][j] := Table[i-1][j]
end if

Ahora para la Tabla [1] [3] ya que nuestra capacidad máxima es igual a nuestro peso actual, tenemos dos opciones.

• Seleccionamos el artículo y agregamos su valor con el valor máximo que podemos obtener de los demás elementos restantes después de tomar este artículo.
• Podemos excluir este artículo.

Entre las dos opciones, elegiremos una de la que podamos obtener el máximo valor. Si seleccionamos el artículo, obtenemos: valor para este artículo + valor máximo del resto de los artículos después de tomar este artículo = 4 + 0 = 4 . Obtenemos 4 (valor del artículo) de nuestra matriz de peso y el 0 (valor máximo que podemos obtener del resto de los artículos después de tomar este artículo) yendo 1 paso arriba y 3 pasos atrás. Eso es la tabla [0] [0] . ¿Por qué? Si tomamos el artículo, nuestra capacidad restante será 3 - 3 = 0 y el artículo restante será el primer artículo. Bueno, si recuerdas la Tabla [0] [0] almacena el valor máximo que podemos obtener si nuestra capacidad fuera 0 y solo tuviéramos el primer elemento. Ahora, si no seleccionamos el artículo, el valor máximo que podemos obtener proviene del paso 1 anterior, que es 1 . Ahora tomamos el máximo de estos dos valores ( 4 , 1 ) y configuramos la Tabla [1] [2] = 4 . Para la Tabla [1] [4] , desde 4 , la capacidad máxima de mochila es mayor que 3 , el peso de nuestro artículo actual, nuevamente tenemos dos opciones. Tomamos max ( Peso [2] + Tabla [0] [4-Weight [2]] , Tabla [0] [4] ) = max ( Peso [2] + Tabla [0] [1] , Tabla [0] [4] ) = max ( 4 + 1 , 1 ) = 5 .

if weight[i] <= j
    w := weight[i]
    Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
end if

Usando estas dos fórmulas, podemos rellenar toda la matriz de la tabla . Nuestra matriz se verá como:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+

Aquí, el último valor que insertamos en nuestra matriz, la Tabla [3] [7] contiene nuestro valor máximo requerido. Este es el valor máximo que podemos obtener si tuviéramos 4 artículos y nuestra capacidad máxima de mochila fuera de 7 .

Una cosa que debemos recordar es que, incluso en la primera fila, el peso puede ser mayor que la capacidad de la mochila. Necesitaremos mantener otra restricción para verificar el valor mientras se llena la primera fila. O simplemente podemos tomar otra fila y establecer todos los valores de la primera fila en 0 . El pseudocódigo se vería así:

Procedure Knapsack(Weight, Value, maxCapacity):
n := Item.size - 1
Table[n+1][maxCapacity+1]
for i from 0 to n
    Table[i][0] := 0
end for
for j from 1 to maxCapacity
    if j >= Weight[0]
        Table[0][j] := Weight[0]
    else
        Table[0][j] := 0
    end if
end for
for i from 1 to n
    for j from 1 to maxCapacity
        if Weight[i] >= j                                            //can't pick the item
            Table[i][j] := Table[i-1][j]        
        else                                                        //can pick the item
            w := Weight[i]
            Table[i][j] := max(w + Table[i-1][j-w], Table[i-1][j])
        end if
    end for
end for
Return Table[n][maxCapacity]

La complejidad del tiempo de este algoritmo es O(n*maxCapacity) , donde n es el número de elementos y maxCapacity es la capacidad máxima de nuestra mochila.

Hasta ahora, hemos encontrado el valor máximo que podemos obtener de nuestro ejemplo. Aún queda una pregunta. ¿Cuáles son los artículos reales? Volveremos sobre los valores en nuestra matriz de tabla para descubrir los elementos que hemos tomado. Seguiremos dos estrategias:

• Para cualquier elemento, si el valor proviene de la posición anterior, no tomamos el elemento actual. Vamos un paso más arriba.
• Si el valor no proviene de la posición anterior, tomamos el artículo. Así que vamos 1 paso arriba y x retrocede, donde x es el peso del artículo actual.

El pseudocódigo será:

Procedure printItems(Table, maxCapacity, Value):
i := Item.size - 1
j := maxCapacity
while j is not equal to 0
    if Table[i][j] is equal to Table[i-1][j]
        i := i - 1
    else
        Print: i
        j := j - weight[i]
        i := i - 1
    end if
end while

Si volvemos sobre nuestro ejemplo, obtendremos:

A partir de esto, podemos decir que podemos tomar los ítems 2 y 3 para obtener el valor máximo.