Me duele el corazón cuando llevo una mochila pesada. ¿Por qué?
Nueve conferencias sobre la mochila de DD Niu
P01: 01 Problema de la mochila
Asunto
Hay n elementos y una capacidad v en un mochila, el costo del artículo I es C y el valor es w. Resolver qué artículos se deben poner en la mochila puede hacer que el costo total de estos artículos no exceda la capacidad de la mochila y el valor total sea el máximo.
Idea básica
Este es el problema de mochila más básico. La característica es que solo hay un elemento de cada elemento, y puedes elegir ponerlo o no.
Utilice subproblemas para definir el estado: es decir, f[v] representa el valor máximo que se puede obtener colocando los primeros I elementos en una mochila con una capacidad de v. La ecuación de transición de estado es: f[v] =max{f[v], f[v-c]+w}.
Esta ecuación es muy importante. Básicamente, todas las ecuaciones relacionadas con el problema de la mochila se derivan de ella. Por lo tanto, es necesario explicarlo en detalle: si solo consideramos la estrategia de poner el primer artículo I, entonces el subproblema de "poner el primer artículo I en una mochila con capacidad V" se puede transformar en uno. que involucra solo el primer ítem I Pregunta para el ítem i-1. Si no se coloca el artículo I-ésimo, entonces el problema se transforma en "Pon el artículo i-1 en una mochila con capacidad V" si se coloca el artículo I-ésimo, el problema se transforma en "Pon el i"; -1 artículo en el restante "En una mochila con capacidad de v-c", el valor máximo que se puede obtener en este momento es f [v-c] más el valor w obtenido al poner el I-ésimo artículo.
Tenga en cuenta que f[v] es significativo si y sólo si hay un subconjunto de los primeros I artículos con costo total V, por lo que después de recurrir de acuerdo con esta ecuación, la respuesta final no es necesariamente f[N ] [V], pero el valor máximo de f[n][0...cinco]. Si se elimina la palabra "cha-cha" de la definición de estado, entonces se agregará un término adicional f[v-1] a la ecuación de transferencia, asegurando así que f[N][V] sea la respuesta final. En cuanto a por qué esto está bien, depende de usted comprenderlo.
Optimizar la complejidad del espacio
La complejidad del tiempo y del espacio del método anterior son O (N*V). La complejidad del tiempo es casi imposible de optimizar, pero la complejidad del espacio puede serlo. optimizado a O(V).
Primero considere cómo implementar las ideas básicas mencionadas anteriormente. Debe haber un bucle principal I = 1...n, y la matriz bidimensional f [0...v] se calcula toda a la vez. Entonces, si solo se usa una matriz f[0..V], ¿podemos garantizar que el estado f[v] que definimos estará representado por f[v] después del ciclo I-ésimo? F[v] se deriva recursivamente de dos subproblemas f[v] y f[v-c]. ¿Está garantizado que los valores de f[v] y f[v -c] se puedan obtener cuando se empuja f[v] (es decir, cuando se empuja f[v] en el I-ésimo bucle principal)? De hecho, esto requiere que presionemos f[v]..0 en el orden v=V para asegurar que f[v-c] guarde el valor del estado f[v-c] al presionar f[v]. El pseudocódigo es el siguiente:
Porque i=1..normal
For v=V..0
f[v]=max{f [v] , f[v-c]+w};
La oración f[v]=max{f[v], f[v-c]} es exactamente equivalente a nuestra ecuación de transferencia f[v]= max{f [v], f[v-c]}, porque ahora f[v-c] es equivalente al f[v-c] original. Si el orden cíclico de V se cambia del orden inverso anterior al orden, entonces f [v] se deriva de f [v-c], lo cual es inconsistente con el significado de esta pregunta, pero es la solución más simple a otra mochila importante. problema P02, por lo que es muy necesario aprender a resolver el problema de la mochila 01 utilizando únicamente matrices unidimensionales.
Resumen
01 El problema de la mochila es el problema de mochila más básico, que contiene los estados y ecuaciones de diseño más básicos del problema de la mochila. Además, otros tipos de problemas de mochila a menudo se pueden transformar en 01 problemas de mochila. Por lo tanto, debemos comprender cuidadosamente el método de dibujo de las ideas básicas anteriores, el significado de la ecuación de transición de estado y, finalmente, cómo optimizar la complejidad del espacio.
P02: Problema completo de la mochila
Sujetos
Hay n tipos de artículos y una mochila con una capacidad V. No hay límite para la cantidad de cada uno artículo. El costo del artículo I es C y el valor es w. Resolver qué artículos poner en la mochila puede hacer que el costo total de estos artículos no exceda la capacidad de la mochila y maximizar el valor total.
Idea básica
Este problema es muy similar al problema de la mochila 01, excepto que cada artículo tiene infinitas piezas. Es decir, desde la perspectiva de cada ítem, la estrategia relacionada con él no es tomar o no tomar dos, sino tomar 0, 1, 2, etc. Si aún seguimos la idea de resolver 01 mochila, dejemos que f [v] represente el peso máximo de los primeros I artículos recién colocados en una mochila con capacidad v, la ecuación de transición de estado aún se puede escribir de la siguiente manera de acuerdo con las diferentes estrategias de cada ítem: f [ v] = max {f [v-k * c]+k * w
Se mejoró la idea básica del problema de la mochila 01 y se obtuvo un método tan claro. Esto muestra que la ecuación del problema de mochila 01 es realmente importante y puede generalizarse a otros tipos de problemas de mochila. Pero todavía intentamos mejorar esta complejidad.
Optimización simple y efectiva
El problema completo de la mochila tiene una optimización simple y efectiva: si los dos elementos I y J satisfacen C = w[j], entonces j no será; elemento eliminado. La exactitud de esta optimización es obvia: pase lo que pase, el J de bajo valor y alto costo puede ser reemplazado por el I barato y de alta calidad, al menos no se puede obtener una solución peor. Para datos generados aleatoriamente, este enfoque tiende a reducir significativamente el número de términos, acelerando así el proceso. Sin embargo, esto no mejora la complejidad del peor de los casos, ya que es posible que los datos especialmente diseñados no puedan desaparecer.
Convertir a solución del problema 01 de mochila.
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 en el problema de la mochila 01 para resolverlo. La idea más simple es que considerando que el artículo V/c es el artículo I más popular, puedo convertir el artículo I en un artículo con el mismo costo y valor que el artículo V/c, y luego resolver el problema de la mochila 01. Esto no mejora en absoluto la complejidad temporal de la idea básica, pero nos da la idea de transformar el problema de la mochila completa en el problema de la mochila 01: descomponer un artículo en varios artículos.
Un método de conversión más eficiente es: dividir el artículo I en varios artículos, con un costo de C * 2 K y un valor de W * 2 K, donde K satisface C * 2 K
Encontrará que este pseudocódigo y el pseudocódigo de P01 solo difieren en el orden del bucle de v. ¿Por qué es factible tal cambio? Primero piense por qué P01 realiza un bucle en el orden inverso de v = V...0. Esto se debe a que se debe garantizar que el estado f [v] en el bucle I-ésimo se derive recursivamente del estado f [v-c]. En otras palabras, esto es precisamente para garantizar que cada ítem se seleccione solo una vez, asegurando que al considerar la estrategia de "seleccionar el ítem I", se base en un subresultado f [v-c] que nunca ha sido seleccionado en el ítem I. . La característica de la mochila completa actual es que cada elemento se puede seleccionar infinitamente, por lo que al considerar la estrategia de "agregar un elemento I", sucede que es necesario que haya un subresultado f [v-c] que pueda haber sido seleccionado en el elemento I, entonces v = Un bucle secuencial de 0 es posible y necesario... es por eso que se creó este programa simple.
Este algoritmo también se puede obtener de otra forma. 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}. ecuación, podemos obtener el pseudocódigo anterior.
Resumen
El problema de mochila completo también es un problema de mochila muy básico. Tiene dos ecuaciones de transición de estado, que se dan en las "Ideas básicas" y el algoritmo "O (VN). "capítulos respectivamente. fuera. Espero que puedas comprender cuidadosamente estas dos ecuaciones de transición de estado, no solo recordarlas, sino también comprender cómo se derivan. Es mejor que descubras cómo obtener estas ecuaciones tú mismo. De hecho, pensar en el significado de su ecuación y cómo obtenerla es una buena manera de profundizar su comprensión de la programación dinámica y mejorar sus habilidades de programación dinámica.
P03: Problema de múltiples mochilas
Sujetos
Hay n tipos de artículos y una mochila con una capacidad v. Hay como máximo n artículos I disponibles, y cada artículo El costo es C y el valor es w. Descubra qué artículos deben colocarse 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
Esta pregunta es muy similar al problema completo de la mochila. Las ecuaciones básicas solo requieren un ligero cambio en las ecuaciones para el problema de mochila completo, ya que hay n+1 estrategias para el elemento I: tomar 0 términos, tomar 1 términos... tomar n elementos. Sea f[v] el peso máximo de los primeros I artículos recién puestos en una mochila con capacidad v, entonces: f [v] = max {f [v-k * c]+k * w
< p | >Convertir al problema de la mochila 01Otro método básico que es fácil de pensar y escribir es convertirlo en la mochila 01: reemplace el artículo I en la mochila 01 con n artículos y luego obtenga el número de elementos El problema de la mochila 01 para ∑n se puede resolver directamente y la complejidad sigue siendo O (V*∑n).
Pero esperamos reducir la complejidad del problema de mochila completo convirtiéndolo en un problema de mochila 01. Aún considerando la idea binaria, consideramos reemplazar el elemento I con varios elementos, de modo que cada estrategia que se pueda adoptar para el elemento I en el problema original (tomar 0...n elementos) puede ser equivalente a reemplazar los siguientes elementos con varios elementos. .Varios artículos. Además, no debe aparecer la estrategia de coger más de n piezas.
El método es: dividir el artículo I en varios artículos, cada artículo tiene un coeficiente, y multiplicar el costo y valor de este artículo por el costo y valor original. Supongamos que estos coeficientes son 1, 2, 4, ..., 2 (k-1), n-2 k+1, y k satisface el entero más grande n-2k+1 >:0. Por ejemplo, si n es 13, entonces este artículo se divide en cuatro artículos y los coeficientes son 1, 2, 4 y 6 respectivamente.
La suma de los coeficientes de estos ítems de división es n, lo que significa que es imposible tomar más de n ítems de primer tipo. Además, este método también garantiza que 0..n pueda representarse mediante la suma de varios coeficientes. Esta prueba se puede discutir en dos partes: 0..2 k-1 y 2 k..n. Esto no es difícil. Espero que lo pienses por ti mismo.
De esta manera, el elemento I se divide en elementos O (log n) y el problema original se transforma en el problema de mochila 01 con una complejidad de O (V * ∑ log n). gran mejora.
Algoritmo O(VN)
El problema de mochilas múltiples también tiene un algoritmo O(VN). Este algoritmo se basa en la ecuación de transición de estado del algoritmo básico, pero el valor de cada estado se puede resolver en tiempo O(1) dividido uniformemente utilizando el método de cola monótona. Dado que el DP de optimización de colas monótonas está más allá del alcance de NOIP, este artículo no entrará en detalles. La primera vez que me enteré de este método fue en la presentación de diapositivas "Ocho preguntas para hombres" de Lou Tiancheng.
Resumen
Aquí vemos el proceso de aumentar la complejidad de un algoritmo de O(V*∑n) a O(V*∑log n). Algoritmo O(VN) que aplica conocimientos más allá del alcance de NOIP. Espero que todos presten especial atención a la idea y al método de "dividir entradas", que demuestren su exactitud por sí mismos y lo implementen con el programa más simple posible.
P04: Problema de tres mochilas mixtas
Problema
Si se mezclan P01, P02 y P03. En otras palabras, algunos artículos solo se pueden llevar una vez (01 mochila), algunos artículos se pueden llevar un número ilimitado de veces (mochila completa) y algunos artículos se pueden llevar con un límite superior (múltiples mochilas). ¿Cómo solucionarlo?
Una mezcla de mochila 01 y mochila completa
Considerando que solo existe una diferencia entre los pseudocódigos dados en P01 y P02, si solo hay dos productos: un producto solo puede se puede tomar una vez y el otro Un producto se puede tomar un número ilimitado de veces, por lo que al aplicar la ecuación de transferencia a cada producto, solo necesita seleccionar el orden o el bucle inverso según la categoría del producto, y la complejidad es O(VN). El pseudocódigo es el siguiente:
Porque i=1..Normal
Si el artículo I-ésimo es la mochila 01
Para v=V. .0
f[v]=max{f[v],f[v-c]+w};
En caso contrario, si el artículo I es una mochila completa.
Para v=0..V
f[v]=max{f[v], f[v-c]+w};
Multi adicional Mochilas
Si algunos artículos se pueden tomar como máximo un número finito de veces, entonces, en principio, también se puede dar una solución O(VN): los artículos con múltiples tipos de mochilas se pueden resolver usando una cola monótona. Pero si no considera los algoritmos fuera del rango NOIP, el método de usar P03 para dividir cada uno de estos elementos en O (log n) 01 elementos de mochila ya es excelente.
Resumen
Algunas personas dicen que las preguntas difíciles son la superposición de preguntas simples. No diré si esta frase es un axioma o no, pero ha quedado plenamente reflejado en esta conferencia. Originalmente, 01 mochila, mochila completa y varias mochilas no eran problemas difíciles, pero después de una combinación simple, apareció tal problema, que definitivamente asustará a muchas personas. Pero siempre que tengas una base sólida y comprendas las ideas de los tres problemas básicos de mochila, podrás dividir los problemas difíciles en otros simples de resolver.
P05: Problema de mochila bidimensional
Problema
El problema de mochila de costo bidimensional significa: para cada artículo, hay dos costos diferentes, elija Este; Se debe pagar el artículo por ambos costos; cada precio tiene un máximo que se puede pagar (capacidad de la mochila). Dígame cómo elegir los artículos para obtener el mejor valor. Sean estos dos costos 1 y 2 respectivamente, y los dos costos requeridos para el elemento I son A y B respectivamente. Los valores máximos que se pueden pagar por los dos tipos de cuotas (dos capacidades de mochila) son V y U respectivamente. Valor del artículo w.
Algoritmo
El costo agrega una dimensión y solo el estado agrega una dimensión. Sea f[v] el valor máximo que se puede obtener cuando el primer artículo I paga los dos precios V y U respectivamente. La ecuación de transición de estado es: f[v]=max{f[v], f[v-a]]+w}. Como se mencionó anteriormente, solo se pueden usar matrices bidimensionales: cuando cada elemento solo se puede tomar una vez, las variables V y U usan un bucle secuencial, y cuando los elementos son como un problema de mochila completo, se usa un bucle inverso. Divida elementos como múltiples problemas de mochila.
Limitaciones en el número total de artículos
A veces las condiciones para el "coste bidimensional" se dan de forma implícita: sólo se pueden tomar m artículos como máximo. Esto equivale efectivamente a una "cantidad de piezas" más por artículo. El número de piezas de cada artículo es 1 y puede pagar hasta m piezas. En otras palabras, sea f [v] [m] el costo de pagar v y elija el valor máximo que puede obtener cuando elige m. piezas como máximo, y luego según los Tipos del ítem (01, completo y múltiple) se actualizan cíclicamente de diferentes maneras, terminando en f[0..V][0..m].
Además, si se le pide "tomar sólo m elementos", la respuesta es f[0..V][M].
Resumen
De hecho, al descubrir un problema que se transforma a partir de un problema de programación dinámica familiar, es una buena idea agregar una línea de latitud al estado original para satisfacer el nuevo restricciones. Un método comúnmente utilizado. 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 costo del artículo I es C y su valor es w , estos elementos se dividen en varios grupos y los elementos de cada grupo entran en conflicto entre sí, por lo que solo se puede seleccionar un elemento como máximo. Resuelve el problema de qué artículos poner en la mochila para que el costo total de estos artículos no exceda la capacidad de la mochila y el valor total sea máximo.
Algoritmo
El problema es que cada grupo de elementos tiene varias estrategias: si seleccionar un elemento del grupo. Es decir, si f[k][v] representa el valor de peso máximo que se puede obtener gastando v en los primeros k grupos de bienes, entonces f [k] [v] = max {f [k-1] [v], f [k -1] [v-c]+w |El ítem I pertenece al ítem k.
El pseudocódigo para usar una matriz unidimensional es el siguiente:
Para todos los k grupos
Porque pertenezco a k grupos.
Para v=V..0
f[v]=max{f[v], f[v-c]+w}
Además, Es muy obvio que la "optimización simple y efectiva" en P02 se puede aplicar a los proyectos de cada grupo.
Resumen
El problema de la mochila agrupada establece un buen modelo al reunir en un grupo varios elementos mutuamente excluyentes.
Muchas variantes del problema de la mochila se pueden transformar en el problema de la mochila agrupada (como P07, a partir del problema de la mochila agrupada, se puede definir mejor el concepto de "términos generalizados", lo cual es muy beneficioso para resolver el problema).
P07: Dependencia del problema de la mochila
Problema simplificado
Existe una cierta relación de "dependencia" entre los elementos de este problema de la mochila. Es decir, I depende de J, es decir, si elige el elemento I, debe elegir el elemento J. Para simplificar, asumimos que ningún elemento depende ni depende de otros elementos, además, ningún elemento depende de múltiples proyectos al mismo tiempo; mismo tiempo.
Algoritmo
Este problema es una extensión del Plan Presupuestario Jinming NOIP2006. Según la formulación de esta pregunta, los artículos que no dependen de otros artículos se denominan "partes principales" y los artículos que dependen de una parte principal se denominan "accesorios". Según los términos simplificados de este problema, todos los proyectos constan de varias partes principales y un conjunto de accesorios que dependen de cada parte principal.
Según la idea general del problema de la mochila, sólo se considera una parte principal y sus conjuntos subsidiarios. Pero hay muchas estrategias disponibles, entre ellas: ninguna, solo la parte principal, un archivo adjunto después de seleccionar la parte principal, dos archivos adjuntos después de seleccionar la parte principal... Muchas estrategias no pueden expresarse mediante ecuaciones de transición de estado. (En realidad, con n adjuntos, el número de estrategias es 2 n+1, lo cual es exponencial).
Considerando que todas estas estrategias son mutuamente excluyentes (es decir, solo se puede seleccionar una estrategia), entonces a El conjunto principal y sus adjuntos en realidad corresponden a un grupo de artículos en P06. Cada estrategia para seleccionar el artículo principal y varios adjuntos corresponde a un artículo en este grupo de artículos, y su costo y valor son la suma de los valores de los mismos. elementos de esta estrategia. Pero esta transformación por sí sola no proporciona un buen algoritmo, porque todavía hay tantos proyectos en el grupo de proyectos como estrategias en el problema original.
Considere una frase de P06: Puede aplicar "una optimización sencilla y eficaz" de P02 a los elementos de cada grupo. Esto nos recuerda que para los proyectos de un grupo de proyectos, todos los proyectos con el mismo costo solo tienen el valor máximo y no afectarán los resultados. Entonces, primero podemos realizar 01 mochila en el "conjunto de accesorios" de la parte principal I y obtener el valor máximo correspondiente f' [0.. Cuando el costo es 0.. v-c en secuencia. Entonces el conjunto de componentes principales y sus accesorios equivale a un conjunto de ítems V-c+1, en el que el valor de los ítems con costo c+k es F'[K]+W. Las estrategias exponenciales originales son redundantes. Después de una mochila de 01, la parte principal I se convierte en un grupo de elementos de V-c+1 y el problema se puede resolver directamente utilizando el algoritmo P06.
Cuestiones más generales
Una cuestión más general es que las dependencias se dan en forma de "bosques" en la teoría de grafos (un bosque es una colección de árboles de múltiples ramas). es decir, los archivos adjuntos de la parte principal aún pueden tener su propio conjunto de archivos adjuntos. La restricción es que cada elemento solo puede depender de un elemento como máximo (solo una parte principal) y no hay dependencia circular.
Para resolver este problema, aún podemos usar el método de convertir cada parte principal y sus archivos adjuntos en un grupo de proyectos. La única diferencia es que, dado que puede haber archivos adjuntos, cada archivo adjunto no puede considerarse como un elemento de la mochila 01 general. Si este accesorio también tiene un conjunto de accesorios, primero se debe convertir en un grupo de artículos, y luego se utiliza el problema de mochila agrupada para resolver el valor accesorio de cada gasto en el grupo de accesorios correspondiente al artículo principal y su conjunto de accesorios.
De hecho, este es un tipo de árbol DP. La característica es que cada nodo padre necesita DP los atributos de sus nodos secundarios una vez para obtener sus propios atributos relacionados. Esto ha tocado el concepto de "bienes amplios". Después de leer P08, encontrará que cada subárbol de este "árbol de dependencia" es equivalente a un término generalizado. Encontrar el término generalizado correspondiente a un subárbol con un nodo como raíz es equivalente a encontrar el término generalizado correspondiente a todos sus subárboles. suma.
Resumen
Fallé con el problema de la mochila NOIP2006. Escribí cientos de líneas de código y no llegué a ninguna parte. Más tarde, después de pensarlo, descubrí que al introducir los conceptos de "grupo de elementos" y "dependencia", puedo profundizar mi comprensión de este problema y resolver su problema de popularización. Consideremos las dependencias extremadamente especiales de ese problema en términos de grupos de términos: un término no puede ser a la vez una parte principal y una parte subsidiaria, y cada parte principal puede tener como máximo dos partes subsidiarias. Se puede encontrar que una parte principal y sus dos anexos equivalen a un grupo de proyectos compuesto por cuatro proyectos, lo que revela parte de la esencia del problema.
Quiero decir: el fracaso no es algo vergonzoso y no ganar nada con el fracaso no es nada.
P08: Términos Generales
Definición
Considera un artículo que no tiene costo o valor fijo, pero su valor varía con la cantidad que le asignas. con costo. Éste es el concepto de mercancías amplias.
Una definición más estricta. En el problema de la mochila con una capacidad de mochila de V, el término generalizado es una función H de números enteros con dominio 0,5. Cuando el costo que se le asigna es V, el valor que se puede obtener es h(v).
Esta definición es un poco abstracta. Otro entendimiento es que el término generalizado es la matriz h[0..cinco]. Dale un costo V y obtendrás el valor h[V].
Un artículo con costo C y valor W, si es un artículo en la mochila de 01, se considera un artículo generalizado, y todos los valores de la función son 0 excepto H (C) = W. Si la función es un elemento en una mochila completa, entonces solo cuando V puede ser divisible por C y todos los demás valores de la función son 0, se puede considerar como una función de h (v) = v/c * w. . Si es el artículo con el mayor número de repeticiones n en la mochila múltiple, entonces la función de su artículo generalizado correspondiente es h(v)=v/c*w solo cuando V se puede dividir por C y v/c
Un grupo de términos puede considerarse como un término generalizado h. Para V..V en 0, si no hay ningún artículo con costo V en el grupo de artículos, entonces h(v)=0; de lo contrario, h(v) es el valor máximo de todos los artículos con costo V. En P07, cada conjunto Las piezas principales y sus accesorios equivalen a un grupo de artículos y, naturalmente, pueden considerarse artículos generalizados.
Suma de artículos generalizados
Si nos enfrentamos a dos bienes generalizados H y L, ¿cómo obtener el máximo valor de estos dos bienes generalizados a un coste determinado? De hecho, para un costo v dado, sólo es necesario enumerar cómo asignar este costo a dos proyectos generalizados. De manera similar, para cada número entero v..v de 0, se puede obtener el valor máximo f(v) del costo v asignado a H y L. Es decir, f (v) = max {h (k)+l (v-k) | 0
Esto puede definir la suma de términos generalizados: H y L son términos generalizados si el término generalizado F. satisface f (v) = max {h (k)+L (v-k) |p>
La definición de términos generalizados muestra que en un problema de mochila, si se usa la suma de dos términos generalizados para reemplazarlos , la respuesta al problema no se verá afectada. De hecho, el proceso de encontrar la respuesta al problema de la mochila en el que todos los términos son términos generalizados es también el proceso de encontrar la suma de todos estos términos generalizados. Suponiendo que esta suma es s, la respuesta es el valor máximo en s[0]..5].
Términos generalizados del problema de la mochila
En el problema de la mochila se pueden dar muchas condiciones, incluido el costo y valor de cada artículo, las relaciones de agrupación y dependencia entre artículos, etc. Pero puede asignar claramente el problema a un proyecto general. Es decir, después de que se den todas las condiciones, podemos averiguar para cada número entero no negativo V: si la capacidad de la mochila es V, ¿cuál es el valor máximo que se puede obtener colocando artículos en la mochila, que puede ser considerados elementos generalizados definidos en el conjunto de números enteros no negativos. Este objeto generalizado (o función cuyo dominio son los números enteros no negativos) contiene información altamente concentrada sobre el problema en sí. En términos generales, después de encontrar el término generalizado de un valor de subdominio (como 0..v), la respuesta final al problema de la mochila se puede obtener en función de este valor de función.
En resumen, en términos generales, resolver el problema de la mochila es resolver una función correspondiente a este problema, que es un término generalizado de este problema. Una forma de resolver un término generalizado es expresarlo como la suma de varios términos generalizados y luego encontrarlo.
Resumen
Se puede decir que esta conferencia es enteramente mi trabajo original. Específicamente, cuando estaba aprendiendo el lenguaje Scheme para programación funcional, examiné varios problemas de mochila desde la perspectiva de la programación funcional. Esta conferencia es realmente abstracta. Quizás haya excedido los requisitos de NOIP en términos del "nivel de abstracción del modelo", por lo que no importa si no la comprende por el momento. Creo que a medida que su viaje en OI se amplíe gradualmente, algún día lo comprenderá.
Quiero decir: "Pensar" es la cualidad más importante de un OIer. Incluso las preguntas simples pueden revelar más después de pensar profundamente.
P09: Cambios en el problema de la mochila.
Todos los diversos problemas de mochila mencionados anteriormente requieren que se obtenga el valor máximo bajo las restricciones de la capacidad de la mochila (costo), pero hay muchas formas flexibles de plantear el problema de la mochila, que vale la pena mencionar aquí. Pero creo que siempre que comprenda profundamente el método para encontrar el valor máximo del problema de la mochila, no es difícil idear un algoritmo incluso si el método del problema cambia.
Por ejemplo, calcula el número máximo de artículos que se pueden colocar o el número máximo de mochilas que se pueden llevar. Estos se pueden obtener basándose en problemas específicos utilizando las ecuaciones anteriores para encontrar los valores de todos los estados (matriz F).
Además, si los requisitos son "valor total mínimo" y "número total mínimo de piezas", simplemente cambie max en la ecuación de transición de estado anterior a min.
Aquí tienes algunas preguntas más diversas.
Esquema de salida
En términos generales, el problema de la mochila requiere un valor óptimo. Si necesita generar este valor óptimo, puede consultar el método de generar soluciones para problemas generales de programación dinámica: registre qué elemento de la ecuación de transición de estado es el valor óptimo para cada estado; en otras palabras, registre qué estrategia se deriva de. Puede utilizar esta estrategia para encontrar el estado anterior y luego avanzar desde el estado anterior.
O tomemos la mochila 01 como ejemplo, la ecuación es f[v]=max{f[v], f[v-c]+w}. Luego use una matriz g[v], suponiendo que g[v]=0 significa que el término anterior de la ecuación se usa al derivar el valor de f[v] (es decir, f[v]=f[v]), g[ v] significa usar el último término de la ecuación. Tenga en cuenta que estos dos elementos representan dos estrategias respectivamente: no elegir el elemento I y elegir el elemento I. Entonces el pseudocódigo del esquema de salida se puede escribir de la siguiente manera (sea el estado final f[N][V]):
i=N
v=V
while(I & gt; 0)
if(g[v]==0)
Imprimir "El elemento I no está seleccionado"
else if(g [v]==1)
Imprimir "El Proyecto que Seleccioné"
v=v-c
Además, durante el proceso Para generar el plan, también puede usar f. El valor de [v] se puede usar para encontrar el término anterior o siguiente de la ecuación en tiempo real, es decir, no es necesario registrar la matriz G g [v. ]==0 en el código anterior se cambia a F[v] == F, g[v] ==1 se cambia a F [v] == F.
La solución óptima con el orden lexicográfico de salida más pequeño
Aquí, "el orden lexicográficamente más pequeño" significa el orden lexicográficamente más pequeño...n después de la elección del elemento 1. Tomemos como ejemplo la solución de generar el orden lexicográfico mínimo de la mochila 01.
En general, para encontrar la solución óptima con el orden lexicográfico más pequeño, sólo es necesario prestar atención a la estrategia de transferencia. En primer lugar, es necesario cambiar ligeramente la definición del subproblema. Observamos que si hay una solución óptima con 1 ítem, entonces la respuesta debe contener 1 ítem y el problema original se transforma en un subproblema con una capacidad de mochila de v-c[1] y un ítem de 2...n. Por otro lado, si la respuesta no contiene 1 ítem, se transforma en un subproblema con una capacidad de mochila de V y un ítem de 2..n. No importa cuál sea la respuesta, los términos del subproblema se definen en la forma. de I..n en lugar de 1..Como se mencionó anteriormente, la definición de estados y ecuaciones de transición deben cambiar. Pero tal vez sea más fácil ordenar los elementos en orden inverso primero, y lo siguiente se describirá basándose en el hecho de que los elementos ya están en orden inverso.
En este caso, se puede evaluar según la clásica ecuación de transición de estado, pero cabe señalar que al ingresar de n a 1, si f[v]==f y f[v]= =f[f-c]+w son ambos verdaderos, entonces el plan de producción debe basarse en este último (es decir, seleccione el elemento I).
Encontrar el número total de soluciones
Para un problema de mochila, dada la capacidad de la mochila, el costo del producto y la relación entre los productos (agrupación, dependencia, etc.), además de dando a cada uno Además del valor máximo obtenido después del valor del artículo, también puede obtener el número total de opciones para llenar la mochila o empacar la mochila a la capacidad especificada.
Para este tipo de problema, generalmente solo necesitas cambiar max en la ecuación de transición de estado a suma. Por ejemplo, si cada artículo es un artículo en la mochila 01, entonces la ecuación de transferencia es f[v]=sum{f[v], f[v-c]+w} y la condición inicial es f[0][0 ]=1.
De hecho, funciona porque la ecuación de transición de estado examina todas las composiciones posibles de la mochila.
Número total de soluciones óptimas
La solución óptima aquí se refiere a la solución con el mayor valor total del producto. Tomemos como ejemplo la mochila 01.
Combinando la idea de encontrar el valor total máximo y el número total de soluciones, el número total de soluciones óptimas se puede obtener de la siguiente manera: f[v] tiene el mismo significado que arriba, g[ v] representa el número total de soluciones óptimas para el subproblema. Por lo tanto, el pseudocódigo de g[v] y f[v] se calcula simultáneamente:
Porque i=1..normal
Para v=0..V
f[v]=max{f[v], f[v-c]+w}
g[v]= 0
if(f[v]==f [v])
Empresa(g[v],g[v]
if(f[ v]==f[v-c]+w)
inc(g[v], g[v-c])
Si es la primera vez que ve un problema de este tipo, Por favor, comprenda atentamente el pseudocódigo anterior.
Resumen
.