Algunos antecedentes. El problema anterior es el problema de la mochila con restricciones. La solución más eficiente del problema de la mochila con o sin restricciones se puede resolver en tiempo pseudopolinómico, aún NP-Hard. Para algunas variaciones, vea https://en.wikipedia.org/wiki/Knapsack_problem#Definition . La primera restricción en esta variación es que el valor de los artículos (bolas) que se colocarán en la mochila (contenedores) no importa. El problema se limita a la cantidad de tiempo que lleva colocar los artículos en la mochila. El problema original requiere que los artículos más valiosos se coloquen en el menor tiempo posible. Otra restricción con esta versión es que los pesos y todos los demás argumentos son enteros. Y la restricción de interés es que los pesoswjdivide para todo j . Nota: el problema de la mochila fraccional se puede resolver en tiempo polinómico, pero no presenta las soluciones más prácticas para el problema original. Este problema utiliza números enteros que se dividen en partes iguales (sin soluciones racionales). Quizás vea ¿Cuál es el problema con el problema de la mochila? .wj+1j
La pregunta principal quizás debería ser "¿este problema sigue siendo NP-Hard cuando no está acotado por un polinomio correspondiente a i , ya que el problema es menos complejo (en P) cuando está acotado? La razón por la que digo esto es porque el problema se puede demostrar que está en P cuando w j está acotado y NP-Hard cuando w j no necesariamente divide w j + 1wjiwjwjwj+1de manera uniforme (los pesos son simplemente aleatorios), todas las restricciones limitan la complejidad de este problema a estas dos condiciones. Estas condiciones (1. el problema de la mochila de peso aleatorio sin la restricción del valor del artículo y 2. el problema de la mochila de peso divisible sin la restricción del valor del artículo) se niegan entre sí en términos de reducción de la complejidad, ya que los cocientes de los pesos pueden ser aleatorios ( especialmente cuando no está limitado), imponiendo así cálculos de tiempo exponencial (esto se mostrará en el ejemplo a continuación). Además, debido a que divide w j + 1 , w j aumenta de tamaño exponencialmente para cada jwjwj+1wjj. Esto se debe a que en lugar de usar elementos ponderados al azar (bolas cuyo peso unitario puede estar limitado a pesos unitarios por debajo de 100 o 50 o incluso 10), la restricción hace que la complejidad del tiempo dependa del número de dígitos de , lo mismo como división de prueba, que es exponencial.wj
Entonces, sí, el programa entero anterior sigue siendo NP-hard incluso cuando divide w j + 1 para todo j . wjwj+1j Y esto se observa fácilmente.
Ejemplo 1: sea y w p sean potencias de dos. Debido a la constante dos, todo el problema se resuelve en tiempo cuadrático, como muestra su ejemplo. Los pesos no son aleatorios y, por lo tanto, el cálculo se resuelve de manera eficiente.n=1wp
Ejemplo 2: dejemos que se defina como w j ∗ p , donde p es el número primo correspondiente a j , de modo que p = 2 , j = 1 : p = 3 , j = 2 , p = 5 , j = 3 , p = 7 , j = 4 , . . . , P , Jwj+1wj∗ppjp=2,j=1:p=3,j=2,p=5,j=3,p=7,j=4,...,P,J. Esto es aplicable, ya que divide w j + 1 para todo j . Obtenemos que cada w j es el producto de todos los primos hasta j . Los valores de los pesos unitarios aumentan como tal: 1 , 2 , 6 , 30 , 210 , 2310 , 30030 , . . . . Como hay un límite ( p j ~ j l o g ( j )wjwj+1jwjj1,2,6,30,210,2310,30030,...pjjlog(j), a través del teorema del número primo), como los cocientes son todos primos, obtenemos la complejidad NP-Intermedio.
Ejemplo 3: dejemos que se defina como w j ∗ R p , donde R p es un número primo elegido al azar de dos a infinito, correspondiente a j . Esto es aplicable a este problema, ya que w j divide w j + 1 para todo j . Obtenemos los primeros 5 cocientes (cayendo aleatoriamente de dos a infinito), como 101 , 2657 , 7 , 3169 , 2wj+1wj∗RpRpjwjwj+1j101,2657,7,3169,2. Vemos que incluso en la quinta bola, el peso tiene once dígitos. Afortunadamente, el quinto cociente fue dos y no un primo del orden de o más. 10100
El ejemplo tres anterior es lo que sucede cuando no está limitado (pesos aleatorios) por un polinomio correspondiente a i . La complejidad del tiempo es exponencial, NP-Hard. Para cierta perspectiva, solo sume todos los pesos, vea si encajan. Pero no hay una solución para resolverlo significativamente más rápido al hacer que los pesos sean divisibles que intentar cada subconjunto para ver si funciona. Después de unas pocas docenas de bolas, aún estás entrando en el reino de incluso los billones de subconjuntos o billones de dígitos.wji