Programación dinámica de la mochila de 0-1 con dos restricciones.
Para un problema de mochila 0-1 con pesos y valores dados de n elementos, y una capacidad de peso máxima W, sé que puede resolverse con un bucle doble anidado utilizando un enfoque dinámico.
Mi pregunta es si decimos que cada uno de los elementos n tiene un valor adicional de “volumen” y una capacidad máxima de volumen V, ¿cómo cambio el algoritmo? ¿El algoritmo se convierte en un bucle triple anidado con una complejidad de tiempo de O(n*W*V)?
davy.ai
Si introducimos una restricción adicional de volumen al problema de la mochila de 0-1, el algoritmo debería ser modificado para acomodar esta nueva restricción. En lugar de iterar a través de los pesos en un bucle anidado doble, ahora iteraríamos a través de los pesos y los volúmenes en un bucle anidado triple.
Específicamente, primero crearíamos una matriz tridimensional de tamaño
n x W x Vpara almacenar el valor máximo que se puede obtener para cada combinación de peso, volumen e índice de elemento. El caso base sería cuandoi=0, en cuyo caso el valor máximo para todas las combinaciones de peso y volumen sería 0 (ya que no hay elementos para agregar). Luego, llenaríamos el resto de la matriz utilizando la siguiente relación de recurrencia:max_value(i, w, v) = max(max_value(i-1, w, v), max_value(i-1, w-w[i], v-v[i]) + value[i])Esta ecuación tiene en cuenta tanto las restricciones de peso como de volumen, asegurando que el elemento solo se agregue a la mochila si hacerlo no excede ninguna de las restricciones.
La complejidad temporal de este algoritmo sería
O(n*W*V), ya que ahora estamos iterando tanto en las dimensiones de peso como de volumen además del índice del elemento. Sin embargo, esta complejidad sigue siendo polinomial y, por lo tanto, factible para la mayoría de los propósitos prácticos.