Hay muchas explicaciones sobre el problema de la mochila en Internet, y yo mismo las he leído y siento que las explicaciones no son fáciles de entender, así que escribí una que es muy fácil de entender.
El problema de la mochila 0-1 es que, dada una capacidad de mochila W y una serie de artículos {peso, valor}, sólo se puede tomar un artículo de cada artículo para obtener el valor máximo.
Utilice programación dinámica para resolver el problema. La regla general de la programación dinámica es:
Bajo la premisa del valor máximo o mínimo de los estados i anteriores, entonces i El valor de. se encuentra el estado.
Aquí definimos una función para representar el estado.
m(1, 2, 3, 4..i)(w) significa que hay elementos No. 1, No. 2, No. 3, No. 4...i, y el La capacidad de la mochila es w. El valor máximo que se puede obtener. Por ejemplo,
Suponga que los elementos 1, 2, 3, 4 y 5 tienen pesos de 2, 2, 6, 5 y 4 respectivamente. Expresados por peso (i), sus valores. son respectivamente 6, 3, 5, 4 y 6 y están representados por el valor (i)
La tabla m(1)(1) solo tiene el elemento No. 1. Cuando la capacidad de la mochila es 1, es el valor máximo. Obviamente,
m(1)(1) = 0, debido a que la capacidad de la mochila es menor que 2, el valor máximo es 0.
m(1)(2) = 6. En este momento, la capacidad de la mochila es igual a 2. Puede contener el artículo número 1. El valor máximo es 6. A continuación,
m(1)(3 ) = 6, m(1)(4) = 6,...m(1)(..) = 6, debido a que solo hay un elemento, el máximo es 6.
m(1,2)(1), m(1,2)(2), m(1,2)(3) significa que hay elementos No. 1 y No. 2, y la capacidad de la mochila es 1 respectivamente, el valor máximo es 2 o 3.
El valor máximo está relacionado con el número de artículos y la capacidad de la mochila.
Hay que enfatizar aquí que m(1, 2, 3,...i)(w) significa que hay 1, 2, 3, 4...i. elegir, puede que no sea posible El valor máximo cuando todos están cargados (limitado por w).
A continuación, analizaremos el valor máximo de los elementos 1, 2, 3...i. Para el i-ésimo artículo, la capacidad de la mochila es W. Hay dos situaciones:
1) Si el i-ésimo artículo no se coloca en la mochila, entonces, en este momento, solo hay 1, 2, 3, 4,,, , i-1 artículos, el valor máximo de la mochila es m(1, 2, 3, 4, 5....i-1) (W). En este momento, no importa qué tan grande sea W, incluso si es tan grande como el universo, la suma de los valores en la mochila es 1, 2, 3, 4, 5 ... i-1. Estos elementos están relacionados.
2) Coloque el elemento i-ésimo. Dado que los artículos i se colocan en la mochila, los artículos 1, 2, 3, 4... i-1 solo pueden ocupar tanto peso como peso W (i). En este momento,
El valor máximo de los elementos 1, 2, 3, 4...i-1 anteriores cuando la capacidad de la mochila es (W-peso(i)) es m(1, 2 , 3......i-1) = max=9
m(1, 2, 3)(8) = max = max=11;
El resto La derivación es la misma. Se puede deducir paso a paso en función de la capacidad de la mochila.