Contenido

Problema de mochila

El problema de la mochila es uno de los 21 problemas NP-Complete de Richard Karp, descritos en su artículo de 1972.

Estados

El problema de la mochila modela una situación análoga al llenado de una mochila, que ya no puede soportar un peso determinado, con todo o parte de un conjunto de objetos dado, cada uno con un peso y un valor. Los artículos metidos en la mochila deben maximizar el valor total, sin exceder el peso máximo.

La forma más común es el problema de la mochila 0-1 (0-1 KP), que restringe el número de copias x_I de cada objeto i hasta un máximo de uno. Sea un conjunto de n objeto, dotado de un peso w_I y de utilidad v_I, y la capacidad de la mochila W, el problema se escribe de la siguiente manera:

maximizar ∑_{i = 1}^no v_I* X_I

sujeto a ∑_{i = 1}^no v_I* X_I ≤ W y x_I ∈ {0.1}.

El problema de la mochila acotada BKP elimina la restricción de limitar el objeto por una limitación acotada por un entero c_I:

maximizar ∑_{i = 1}^no v_I* X_I

sujeto a ∑_{i = 1}^no v_I* X_I ≤ W y x_I ∈ {0,…, c_I}.

El problema ilimitado de las mochilas UKP no impone restricciones al número de copias de cada artículo.

maximizar ∑_{i = 1}^no v_I* X_I

sujeto a ∑_{i = 1}^no v_I* X_I ≤ W y 0≤x_I .

Hay muchas otras variantes del problema de la mochila que se describen en otra página. por favor refiérase a Reducción de polinomios.

Métodos de resolución

Algoritmo codicioso

La idea es agregar los objetos más efectivos como prioridad, hasta que se sature la bolsa:

 Ordene los objetos en orden decreciente de eficiencia w_conso: = 0

para I de 1 Para no
  si w [i] + w_conso ≤ W entonces
    x [i]: = 1 w_conso: = w_conso + w [i]
  de lo contrario
    x [i]: = 0
  terminara si
final para

Programación dinámica

El problema de la mochila tiene la propiedad de una subestructura óptima, es decir, que podemos construir la solución óptima del problema de k variables a partir del problema de k - 1 variable.

Deja F_k(E) el mejor costo para llenar una bolsa de tamaño E con la k
primeros objetos. La recurrencia muestra que F_k(E) = máx. {F_{k - 1}(E), F_{k - 1}(E - w_k) + v_k},

de hecho, la adición de un nuevo objeto aumenta o no el mejor costo. Si el nuevo objeto no se agrega a la bolsa, F_k(E) es igual a F_{k - 1}(MI). En el caso en el que el nuevo objeto ofrece una mejor utilidad, es decir, en el caso en el que el objeto no está presente pero la bolsa (sin el objeto) tiene suficiente espacio para acomodar el nuevo elemento, y es óptimo (es decir, la fórmula F_{k - 1}(E - w_k)), luego F_k(E) es igual a F_{k - 1}(E - w_k) + v_k, v_k siendo la utilidad del nuevo objeto añadido a la bolsa descrita anteriormente.

Por lo tanto, buscamos calcular F_no(W), siendo n el número total de objetos y W el tamaño máximo de la mochila estudiada.

para vs de 0 Para W hacer
  T [0, c]: = 0
final para

para I de 1 Para no hacer
  para vs de 0 Para W hacer
    si c> = w [i] entonces
      T [i, c]: = max (T [i-1, c], T [i-1, cw [i]] + p [i])
    de lo contrario
      T [i, c]: = T [i-1, c]
    terminara si
  final para
final para

Tenemos los siguientes elementos: C = 8, y cinco objetos descritos en
la mesa de abajo

I	1	2	3	4	5
Pi	3	4	5	4	2
u_i	15	18	20	12	6

Obtenemos la siguiente tabla de resultados de la mochila:

E \| yo	1	2	3	4	5
0	0	0	0	0	0
1	0	0	0	0	0
2	6	6	6	6	6
3	15	6	6	6	6
4	15	18	12	12	6
5	21	20	20	12	6
6	24	24	20	18	6
7	33	26	26	18	6
8	35	30	26	18	6

La solución óptima de 25 se obtiene con los elementos 1 y 3 según el segundo
algoritmo de la mochila:

k	1	2	3	4	5
mi	8	5	5	0	0
x [k]	1	0	1	0	0

conso = conso_1 + conso_3 = 8.