¿Cómo abordaría el problema de la mochila en una situación de programación dinámica si ahora tiene que limitar el número de elementos en la mochila por una constante ? Este es el mismo problema (peso máximo de , cada artículo tiene un valor peso ) pero solo puede agregar artículo (s) a la mochila y obviamente necesita optimizar el valor de la mochila.W v w p
¿Necesitamos una tercera dimensión o podríamos encontrar otro enfoque sin ella? Intenté simplemente agregar la cantidad de elementos en la mochila en la celda y tomar el valor máximo al final con la cantidad de elementos <= pero no es la MEJOR solución.
algorithms
optimization
dynamic-programming
knapsack-problems
usuario11536
fuente
fuente
Respuestas:
Muy buena pregunta!
Tienes razón dos veces:
A continuación, supongo que está familiarizado con la solución basada en programación dinámica. En particular, no discutiré cómo recorrer la tabla hacia atrás para determinar la solución .
Centrémonos primero en el caso típico: la cantidad de artículos no está restringida . En este caso, simplemente construye una tabla donde contiene el valor óptimo cuando la capacidad total de la mochila es igual a y solo se consideran los primeros elementos. De aquí:T i , j i jT Ti,j i j
donde y representan el peso y el valor del elemento -th respectivamente. Si es la capacidad total de su mochila y hay un total de elementos, proporciona la solución óptima . Se sabe que este algoritmo se ejecuta en tiempo pseudopolinomial y una de sus bellezas es que solo considera aquellas combinaciones que se ajustan a la capacidad máxima.wj vj j C N TC,N
Sin embargo, esto no es suficiente al agregar su restricción: un número máximo de elementos . La razón es que la fórmula de recurrencia anterior no tiene en cuenta las diferentes combinaciones de elementos:p
De modo que una primera solución consiste en agregar una tercera dimensión. Para su caso, deje que sea la solución óptima cuando la capacidad de la mochila es , solo se consideran los primeros elementos y no se permite colocar más de elementos en la mochila. Ahora,Ti,j,k i j k
La primera expresión debe ser clara. El segundo funciona ya que la capa de la tabla realiza un seguimiento de la mejor combinación de elementos entre los primeros como se requiere anteriormente.(k−1) T (k−1) (j−1)
Una implementación eficiente de este algoritmo no necesita calcular para todos los . Tenga en cuenta que las relaciones de recurrencia anteriores relacionan la capa con y, por lo tanto, es posible alternar entre dos capas sucesivas (por ejemplo, si está interesado en la solución óptima con , solo use dos capas consecutivas: 0 y 1, 1 y 2, 2 y 3, 3 y 4 y ya está). En otras palabras, este algoritmo toma el doble de memoria requerida por el enfoque tradicional basado en la programación dinámica y, por lo tanto, todavía puede ejecutarse en tiempo pseudo-polinomial.Ti,j,k k k (k−1) k=4
¡Tenga en cuenta, sin embargo, que esta no es la única solución! Y hay otro que puede encontrar más elegante. En las fórmulas anteriores, recuperamos la solución óptima que consistía en no más de elementos entre los primeros como . ¡Sin embargo, debe quedar claro que esto es exactamente igual a simplemente usando la tabla original! es decir, la solución óptima con no más de ítems también puede recuperarse considerando las soluciones óptimas con 1 ítem, 2 ítems, 3 ítems, ...(k−1) (j−1) Ti,j−1,k−1 maxp=0,j−1{Ti,p} k (j−1) elementos ... Para que esta formulación funcione, también debe realizar un seguimiento del número de elementos considerados en cada solución parcial para que necesite dos enteros por celda. Esta ocupación de memoria da como resultado exactamente los mismos requisitos de memoria del algoritmo mostrado anteriormente (usando una tercera dimensión en forma de capas )k .
Espero que esto ayude,
fuente