Problema de mochila

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 xI de cada objeto i hasta un máximo de uno. Sea un conjunto de n objeto, dotado de un peso wI y de utilidad vI, y la capacidad de la mochila W, el problema se escribe de la siguiente manera:

maximizar ∑i = 1no vI* XI
sujeto a ∑i = 1no vI* XI ≤ W y xI ∈ {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 cI:

maximizar ∑i = 1no vI* XI
sujeto a ∑i = 1no vI* XI ≤ W y xI ∈ {0,…, cI}.

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

maximizar ∑i = 1no vI* XI
sujeto a ∑i = 1no vI* XI ≤ W y 0≤xI .

problème du sac à dos 0-1 knapsack NP réduction

Hay muchas otras variaciones del problema de la mochila que se describen en otra página. Consulte 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 Fk(E) el mejor costo para llenar una bolsa de tamaño E con la k
primeros objetos. La recurrencia muestra que Fk(E) = máx. {Fk - 1(E), Fk - 1(E - wk) + vk},

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, Fk(E) es igual a Fk - 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 Fk - 1(E - wk)), luego Fk(E) es igual a Fk - 1(E - wk) + vk, vk siendo la utilidad del nuevo objeto añadido a la bolsa descrita anteriormente.

Por lo tanto, buscamos calcular Fno(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 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.

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: