Prueba para la dureza NP de la minimización simultánea y la maximización de un subconjunto ponderado

Question

Estoy trabajando en un problema definido como el siguiente

Dado un conjunto de $ n $ elementos llamados $ r \ subesteq \ mathbb {n} \ timbb {n} \ times \ mathbb {n} \ times \ mathbb { N} $ y números $ z, g \ in \ mathbb {n} $ , donde $ z $ es una medida de nuestros recursos y $ g $ es nuestra recompensa mínima necesaria, ¿hay un conjunto $ r '\ subesteceq r $ , para que $ \ sum _ {(z, g) \ in r'} z \ leq z $ y $ \ SUM _ {(Z, G) \ en R '} G \ GEQ G $ ?

Quiero mostrar su integridad NP y ha demostrado que ya está en NP. Estoy luchando con la dureza NP. Mis conocidos problemas de NP-DURS son el sábado, 3SAT, partición, suma de subconjunto y embalaje del contenedor.

Mi lucha parece ser principalmente con el hecho de que tenemos que equilibrar dos valores diferentes, el costo y la recompensa. Este no es el caso en ninguno de los problemas relacionados con los problemas que mencioné y no puedo pensar en cómo modelar esto en SAT o 3SAT. ¿Que me estoy perdiendo aqui? ¿Cómo puedo mostrar la dureza NP y, como tal, la integridad de NP de este problema utilizando solo estos problemas dados?

Answer 1

Esto me suena como el problema de mochila donde

• $ z $ es el peso de cada elemento,
• $ z $ es la capacidad de la mochila,
• $ g $ el valor del artículo, y
• $ g $ el valor a alcanzar.

El problema es NP-Complete pero solucible, usando programación dinámica, en Pseudo-polinomial Tiempo $ O (n \ CDOT W) $ donde $ w=max _ {(z, g) \ in r} (g) $ .

Puede probar que el problema de Knapsack es NP-completo al reducir desde la problema de suma de subsetal . De hecho, la suma de subconjunto es un caso especial de mochila donde $ z= g $ ; El "peso" de cada problema es el mismo que su "valor".