Si la mochila es 0/1, no hay necesidad de mencionar que está limitada.
No existe tal algoritmo conocido, porque al igual que un problema normal de mochila 0/1, la variante multidimensional todavía es NP-completa y para todos los propósitos prácticos [math] \ text {P} \ ne \ text {NP} [/ math] . Agregar dimensiones no facilitó exactamente el problema.
Sin embargo, existe un algoritmo que se ejecuta en tiempo polinómico con respecto a los límites y los límites de peso, en oposición al tamaño de la entrada. Esto no está en PTIME (que es lo mismo que solo P), pero aún es un algoritmo razonablemente rápido.
- ¿Cuál es la explicación intuitiva de agregar bordes traseros en el gráfico en el algoritmo Ford-Fulkerson?
- ¿Qué es el mapa de bits? ¿Dónde lo usamos?
- Cómo determinar todas las condiciones, suposiciones y limitaciones para un código C # dado que calcula el valor promedio de una matriz de diferentes números
- ¿Puede una computadora generar un número verdaderamente aleatorio?
- ¿Qué es segmentar segmentado?
Deje que [math] DP (c, \ vec {w}) [/ math] represente el valor máximo que puede obtener utilizando solo los primeros elementos [math] c [/ math] mientras que cada dimensión de peso de los elementos utilizados es exactamente igual a dimensión respectiva en el vector [math] \ vec {w} [/ math].
Tenga en cuenta que [matemáticas] DP (0, \ vec {0}) = 0 [/ matemáticas] y [matemáticas] DP (i, \ vec {w}) = \ max_ {j <i} DP (j, \ vec { w} – \ vec {w_i}) + v_i [/ math], donde [math] \ vec {w_i} [/ math] es el vector de peso del elemento [math] i [/ math] -th y [math] v_i [/ math] es el valor del elemento [math] i [/ math] -th.
La solución al problema será el máximo de [math] DP (c, \ vec {w}) [/ math] para todos los valores posibles de [math] c [/ math] y [math] \ vec {w} [ /matemáticas].
