Cada vez que llevo una mochila demasiado pesada, me duele el corazón. ¿Por qué?
Nueve conferencias sobre la mochila DD Bull
P01: 01 Problema de la mochila
Problema
Hay N artículos y una mochila con capacidad V, el costo del i-ésimo artículo es c. El i-ésimo artículo tiene un costo de c y un valor de w. Resuelva el problema de los artículos que se pueden cargar en la mochila para que el costo total de estos artículos no exceda la capacidad de la mochila y el valor total sea el mayor.
Idea básica
Este es el problema de mochila más básico. Su característica es que solo hay un elemento de cada elemento, y puedes elegir ponerlo o no.
Utilice subproblemas para definir el estado: f[v] representa el valor máximo que se puede obtener colocando los primeros i artículos en la mochila con capacidad v. La ecuación de transición de estado es: f[v ] es el valor máximo que se puede obtener poniendo los primeros i artículos en una mochila con capacidad v, entonces su ecuación de transición de estado es: f[v]=max{f[v],f[v-c]+w}.
Esta ecuación es tan importante que básicamente todas las ecuaciones relacionadas con los problemas de mochilero se derivan de ella. Por lo tanto, es necesario explicar en detalle: si solo consideramos la estrategia del i-ésimo artículo (ponerlo o no ponerlo), entonces el subproblema "Colocar el primer i artículo en la mochila con capacidad v " se puede transformar en un subproblema que involucra solo un problema con los primeros elementos i-1. Si no se coloca el i-ésimo artículo, el problema se transforma en "Pon los primeros i-1 artículos en la mochila con capacidad v" si se coloca el i-ésimo artículo, el problema se transforma en "Pon el primer i"; -1 artículos en la mochila con capacidad v" Ponlo en el resto de la mochila con capacidad v - c". El valor máximo que se puede obtener es f [v-c] más el valor w obtenido al poner el i-ésimo artículo en la mochila.
Tenga en cuenta que f[v] solo tiene sentido si y solo si hay un subconjunto de los i elementos actuales con una suma de costos v. Entonces, después de la ecuación recursiva, la respuesta final no es necesariamente f[N][V], sino el valor máximo de f[N][0...V]. Si se elimina la palabra "cha" de la definición del estado, se debe agregar un término adicional f[v-1] a la ecuación de transición para garantizar que f[N] [V] sea la respuesta final. En cuanto a por qué se puede hacer esto, depende de lo que pienses.
Optimizar la complejidad del espacio
La complejidad del tiempo y del espacio del método anterior son O (N * V). La complejidad del tiempo básicamente ya no es optimizable, pero la complejidad del espacio puede serlo. optimizado a O(V).
Primero considere cómo implementar la idea básica anterior. Debe haber un bucle principal i = 1... N, que cuente todos los valores de la matriz bidimensional f [0... V] uno a la vez. Entonces, si solo hay una matriz f [0..V], ¿podemos garantizar que el estado f [v] representado por f [v] al final del i-ésimo ciclo sea el estado f [v] que definimos? ? f [v] se deriva recursivamente de dos subproblemas f [v] y f [v-c]. ¿Podemos garantizar eso cuando presionamos f [v] (es decir, cuando presionamos f [v] en el i-ésimo principal)? bucle) ¿Podemos obtener los valores de f [v] y f [v -c]? De hecho, esto requiere que presionemos f[v] en el orden v=V...0 en cada bucle principal, para garantizar que cuando se presiona f[v], f[v-c] mantenga el estado f[v] -c ] valor.
El pseudocódigo es el siguiente:
for i=1...N
for v=V...0
f[v]=max {f[ v],f[v-c]+w};
La frase f[v]=max{f[v],f[v-c]} es la misma que nuestra ecuación de transferencia f[v ]=max{ f[v],f[],f[],f[],f[],f[],f[],f[v-c]} son completamente equivalentes porque f[v-c] ahora es equivalente al f[v-c] original. Si el orden del ciclo de v se cambia del orden inverso anterior al orden, entonces se deduce f [v] de f [v-c], lo cual es inconsistente con el significado de la pregunta, pero es la solución más simple a otro importante problema de mochila en P02 Por lo tanto, es muy necesario aprender a resolver el problema de mochila 01 usando solo matrices unidimensionales.
Resumen
01 El problema de la mochila es el problema de la mochila más básico. Contiene las ideas más básicas para diseñar los estados y ecuaciones del problema de la mochila. Los problemas a menudo se pueden resolver. Convierta a la solución del problema de 01 mochila. Por lo tanto, debemos comprender cuidadosamente los métodos de pensamiento básicos anteriores, la importancia de la ecuación de transición de estado y, finalmente, cómo optimizar la complejidad del espacio.
P02: El problema de la mochila completa
Problema
Hay N artículos y una mochila de capacidad V. Cada artículo tiene un número infinito de artículos disponibles. Encuentra los artículos que se pueden cargar en la mochila de manera que la suma de los costos de estos artículos no exceda la capacidad de la mochila y la suma de los valores sea máxima.
Idea básica
Este problema es muy similar al problema de la mochila 01, excepto que el número de cada artículo es infinito. La diferencia es que la cantidad de cada artículo es ilimitada. Es decir, desde la perspectiva de cada ítem, la estrategia relacionada con él ya no es tomar o no tomar, sino tomar 0 ítems, tomar 1 ítem, tomar 2 ítems…, y muchos otros tipos. Si seguimos la misma idea al resolver la mochila 01 y dejamos que f[v] represente el peso máximo de los primeros i elementos que caben en una mochila con una capacidad de v, entonces todavía podemos usar diferentes estrategias para escribir transiciones de estado para cada elemento, por ejemplo: f[v]=max{f[v-k*c]+k*w|0<=k*c<=v}. Esto es lo mismo que el problema de la mochila 01, que requiere resolver estados O (N * V), pero el tiempo para resolver cada estado ya no es constante, el tiempo para resolver el estado f [v] es O (v / c); , y la complejidad total es mayor que O (VN).
Al refinar la idea básica del problema de la mochila 01, se puede obtener un método tan claro. Esto muestra que las ecuaciones del problema de mochila son realmente importantes y pueden generalizarse a otros tipos de problemas de mochila. Sin embargo, todavía estamos trabajando para mejorar esta sofisticación.
Un método de optimización simple y efectivo
Para el problema completo de la mochila, existe un método de optimización muy simple y efectivo: si los dos elementos i y j satisfacen c<=c[j ] y w>=w[j], el elemento j se eliminará de la consideración. La corrección de este enfoque de optimización es obvia: en cualquier caso, si un valor j pequeño y más costoso puede intercambiarse por un valor i bueno y menos costoso, entonces la solución al menos no es peor. Para datos generados aleatoriamente, este enfoque tiende a reducir significativamente el número de piezas del proyecto, acelerando así las cosas. Sin embargo, esto no mejora la complejidad del peor de los casos, ya que con datos especialmente diseñados es posible no eliminar ni un solo elemento.
Convierta a la solución del problema de la mochila 01
Dado que el problema de la mochila 01 es el problema de la mochila más básico, podemos considerar convertir el problema de la mochila completo al problema de la mochila 01 para resolverlo. . La idea más simple es considerar que el artículo i-ésimo se selecciona como máximo piezas V/c, por lo que podemos convertir el artículo i-ésimo en piezas V/c con costo y valor constantes, y luego resolver este problema de 01 mochila. Esto no mejora en absoluto la complejidad temporal de la idea básica, pero nos da la idea de convertir el problema de mochila completo en el problema de mochila 01: dividir un proyecto en varios proyectos.
Una transformación más eficiente es dividir el i-ésimo artículo en varios artículos con costo c*2^k y valor w*2^k, donde k satisface c*2^k
Encontrará que este pseudocódigo es diferente del pseudocódigo de P01 solo en el orden del bucle de v. ¿Por qué hay tal cambio? Primero piense por qué P01 realiza un bucle en el orden inverso de v=V..0. Esto es para garantizar que el estado f[v] en el i-ésimo bucle se derive recursivamente del estado f[v-c]. En otras palabras, esto es para garantizar que cada ítem se seleccione solo una vez y que la estrategia "seleccionar el i-ésimo ítem" se considere en términos del subresultado f[v-c] para el cual el i-ésimo ítem no ha sido seleccionado. aún no ha sido seleccionado. Ahora bien, la característica de una bolsa completa plegada es que la cantidad de cada artículo es infinita, por lo que la estrategia de "agregar el i-ésimo artículo" requiere un subresultado f[v-c] que pueda haber seleccionado el i-ésimo artículo, por lo que también se debe utilizar un bucle secuencial de v= 0...V. Por eso funciona este sencillo programa.
Este algoritmo también se puede derivar de otra idea. Por ejemplo, la ecuación de transición de estado en la idea básica se puede transformar de manera equivalente en la siguiente forma: f[v]=max{f[v],f[v-c]+w}, que se implementa en forma de un matriz dimensional, obteniendo así el pseudocódigo anterior.
Resumen
El problema de mochila completo también es un problema de mochila muy básico. Hay dos ecuaciones de transición de estado, que se describen en las "Ideas básicas" y el "Algoritmo O (VN). " secciones respectivamente. dadas en . Espero que todos puedan comprender seriamente estas dos ecuaciones de transición de estado, no solo recordarlas, sino también comprender su proceso de derivación, y es mejor encontrar formas de obtenerlas usted mismo. De hecho, pensar en el significado de la ecuación y cómo obtenerla para cada pregunta de programación dinámica es una buena manera de profundizar su comprensión de la programación dinámica y mejorar sus capacidades de programación dinámica.
P03: Problema de múltiples mochilas
Problema
Hay N artículos y una mochila con capacidad V. El i-ésimo artículo tiene como máximo n artículos. Encuentre los artículos que se pueden cargar en la mochila para que el costo total de estos artículos no exceda la capacidad de la mochila y el valor total sea el mayor.
Algoritmo básico
Este problema es muy similar al problema de mochila completo. Dado que hay n+1 estrategias para el i-ésimo artículo: tomar 0 artículos, tomar 1 artículo, ... tomar n artículos, la ecuación básica es solo una ligera modificación de la ecuación para el problema de la mochila completa. Entonces: f[v]=max{f[v-k*c]+ k*w|0<=k<=n}. La complejidad es O(V*∑n).
Conversión al problema de la mochila 01
Otro enfoque básico sobre el que vale la pena pensar y escribir es la conversión a la solución de la mochila 01: reemplazar el elemento i-ésimo con el 01- mochila con n elementos, se puede obtener un problema de 01 mochila con ∑n elementos, que se puede resolver directamente y la complejidad sigue siendo O (V * ∑n).
Pero esperamos que después de transformarlo en un problema de mochila 01, la complejidad se pueda reducir como el problema de mochila completa. Aún considerando la idea binaria, consideramos reemplazar el i-ésimo elemento con una cantidad de elementos, de modo que en el problema original cada estrategia en la que el i-ésimo elemento sea deseable (tomando 0...n elementos) pueda ser equivalente. a tomar varios artículos. Además, no puede surgir ninguna estrategia que requiera más de n piezas.
El método consiste en dividir el i-ésimo artículo en varios artículos. Cada artículo tiene un coeficiente, que es el costo y el valor del artículo multiplicado por el costo y el valor originales. Sean estos coeficientes 1,2,4,...,2^(k-1),n-2^k+1, donde k es el entero más grande tal que n-2^k+1>0. Por ejemplo, si n es 13, divida el elemento en cuatro elementos con coeficientes 1, 2, 4 y 6.
La suma de los coeficientes de estos términos dividida por n muestra que es imposible tomar más de n términos del mismo tipo. Además, este método también garantiza que cada número entero entre 0...n pueda representarse mediante la suma de varios coeficientes. Esta prueba se puede obtener entre 0...2^k-1 y 2^k.. Derivado de dos. diferentes discusiones sobre .n. No es difícil de entender y espero que lo pienses un poco y lo pruebes tú mismo.
De esta manera, el i-ésimo proyecto se divide en proyectos O(log n), transformando así el problema original en el problema de mochila 01 con una complejidad de O(V*∑log n). Es una gran mejora.
O(VN)
El problema de mochilas múltiples también tiene un algoritmo O(VN). El algoritmo se basa en las ecuaciones de transición de estado del algoritmo básico, pero utiliza un enfoque de cola monótona para que el valor de cada estado pueda resolverse incluso en tiempo O(1). Dado que la optimización de DP mediante colas monótonas está fuera del alcance de NOIP, no se tratará en este artículo. La primera vez que aprendí sobre este método fue en la presentación de diapositivas "Ocho preguntas para hombres" de T.C.
Resumen
Aquí, vimos el proceso de aumentar la complejidad del algoritmo de O(V*∑n) a O(V*∑log n), y aprendimos que Some O( VN) los algoritmos aplican conocimientos más allá del alcance de NOIP. Espero que todos presten especial atención a la idea y el método del "subelemento", demuestren su exactitud por sí mismos y lo implementen con el programa más simple posible.
P04: Problema de mezclar tres mochilas
Problema
Si mezclas P01, P02 y P03. En otras palabras, hay elementos que solo se pueden recuperar una vez (01 mochila), elementos que se pueden recuperar un número ilimitado de veces (mochila completa) y elementos que se pueden recuperar hasta un límite superior (múltiples mochilas). ¿Cómo debería solucionarse este problema?
Mezclando 01 mochilas y mochilas completas
Considerando que solo hay una diferencia entre el último pseudocódigo dado en P01 y P02, si solo hay dos tipos de artículos: un tipo solo puede Una vez que se extrae un artículo, el otro tipo es un artículo que se puede extraer infinitas veces, luego, al aplicar la ecuación de transferencia a cada artículo, solo necesita elegir un bucle secuencial o un bucle inverso según la categoría del artículo, y la complejidad es O (VN). El pseudocódigo es el siguiente:
para i=1...N
Si el i-ésimo artículo es 01 mochila
para v=V. ..0
f[v]=max{f[v],f[v-c]+w};
En caso contrario, si el i-ésimo artículo es una mochila completa
para v=0...0
f[v]=max{f[v],f[v-c]+w}
De lo contrario, si el i-ésimo artículo es Mochila completa
para v=0.V
f[v]=max{f[v],f[v-c]+w}; /p>
Agregar varias mochilas
Si algunos artículos solo se pueden llevar un número limitado de veces, entonces, en principio, se puede dar una solución O(VN): para los tipos de artículos que se encuentran con múltiples mochilas, es suficiente resolver usando una cola monótona. Sin embargo, dividir cada uno de estos elementos en O (log n) 01 elementos de mochila en P03 ya es óptimo si no consideramos algoritmos que están fuera del alcance de NOIP.
Resumen
Algunas personas dicen que los problemas difíciles se componen de problemas fáciles. No importa si esta afirmación es axiomática o no, pero está bien representada en esta conferencia.
Originalmente, 01 mochila, mochila completa y varias mochilas no eran problemas difíciles, pero después de simplemente combinarlas, nos surgió una pregunta que sería desalentadora para muchas personas. Sin embargo, siempre que tenga una base sólida y comprenda las ideas de los tres problemas básicos de mochila, podrá dividir los problemas difíciles en otros simples de resolver.
P05: El problema de la mochila con costos bidimensionales
Problema
El problema de la mochila con costos bidimensionales significa que cada artículo tiene dos costos diferentes,. Para elegir un artículo se deben pagar estos dos costos, y cada costo tiene un valor máximo que se puede pagar (la capacidad de la mochila). ¿Cómo elegir artículos para obtener el máximo valor? Supongamos que los dos costos son el costo 1 y el costo 2 respectivamente, y los dos costos del elemento i son a y b respectivamente. Los valores máximos que se pueden pagar por cada coste (la capacidad de dos mochilas) son V y U respectivamente.
Algoritmo
El costo se suma en una dimensión y el estado también se suma en una dimensión. Sea f [v] el valor máximo que se puede obtener pagando v y u respectivamente por los primeros i elementos. La ecuación de transición de estado es: f [v]=max{f[v],f[v-a]]+w}. Al igual que con el método anterior, puede usar una matriz bidimensional: cuando cada elemento solo se puede tomar una vez, las variables v y u usan un bucle secuencial cuando el elemento tiene un problema de mochila completo, etc., las variables v; y usas un bucle inverso. Divida el artículo cuando sea el mismo que el artículo en el problema de múltiples mochilas.
Límites en el número total de artículos
A veces la condición de "coste bidimensional" está implícita en el sentido de que como máximo se pueden obtener M artículos. En otras palabras, represente f[v][m] el valor máximo que se puede obtener pagando el costo de v y extrayendo como máximo m artículos, y luego haga un bucle de diferentes maneras según el tipo de artículo (01, completo, múltiples) Actualizar los costos del proyecto. Utilice diferentes métodos para realizar bucles y actualizaciones, y finalmente encuentre la respuesta en el rango f[0...V][0...M].
Alternativamente, si el requisito es "tomar exactamente M elementos", la respuesta se encuentra en el rango f[0...V][M].
Resumen
De hecho, cuando se busca una transformación de un problema de programación dinámica familiar, es común agregar paralelos al estado original para satisfacer las nuevas restricciones. Espero que pueda obtener una comprensión preliminar de este método a partir de esta conferencia.
P06: Problema de Mochilas Agrupadas
Problema
Hay N artículos y una mochila con capacidad V. El i-ésimo artículo tiene un costo de c y un valor de w. Los elementos se dividen en grupos, los elementos de cada grupo entran en conflicto entre sí y no se puede seleccionar más de uno. Resuelva los artículos que se pueden cargar en la mochila para que el costo total de estos artículos no exceda la capacidad de la mochila y el valor total de estos artículos sea el mayor.
Algoritmo
En este problema, cada grupo de elementos tiene varias estrategias: elegir un elemento del grupo o elegir ninguno. Es decir, sea f[k][v] el peso máximo que se puede obtener gastando el costo v en los artículos de los primeros k grupos, entonces f[k][v]=max{f[k-1 ][v ],f[k-1][v-c]+w|el elemento i pertenece al késimo grupo}.
El pseudocódigo para utilizar una matriz unidimensional es el siguiente:
Para todos los k grupos
Para todos los i pertenecientes a k grupos
Para v =V...0
f[v]=max{f[v],f[v-c]+w}