Se proporciona el conjunto . Para cada elemento , tenemos peso y costo . El objetivo es encontrar el subconjunto de tamaño que maximice la siguiente función objetivo: .e i w i > 0 c i > 0 M k ∑ e i ∈ M w i + ∑ e i ∉ M w i c i
¿El problema es NP-duro?
Dado que la función objetivo parece extraña, es útil explicar una aplicación de la función objetivo.
Supongamos que tenemos n elementos a y hay copias de cada objeto en nuestro inventario. Tenemos algunos clientes y están interesados en estos objetos en proporción con su peso , lo que significa que el objeto con mayor es más popular. Tenemos un sistema de venta en línea y necesitamos responder correctamente a las solicitudes de nuestros clientes. No podemos reconocer objetos por sus formas (¡todos se ven iguales!). Pero tenemos un clasificador para encontrarlos. Cada clasificador se puede usar para detectar copias de un objeto. Nuestro objetivo es ejecutar k clasificador para maximizar la satisfacción de nuestros clientes.e n c i e i w i w i
PD: Puede ser útil pensar en el caso de que para todo ; sin embargo, no estoy seguro. [ ¡Estaba equivocado sobre esto! Está en P por esta suposición ]i ≤ n
fuente
Respuestas:
La respuesta a continuación observa que un caso especial del problema se puede resolver en tiempo polinómico. Esto no responde completamente la pregunta en la publicación, pero puede dar una idea de lo que podría ser necesario para una prueba de dureza NP, y puede provocar un interés adicional en la publicación ...
Observación. El problema en el poste tiene un algoritmo que, dado cualquier caso en el que cada es un número entero, carreras en polinomio tiempo en n y D = Σ i c i .Cyo norte D = ∑yoCyo
Bosquejo de prueba. Arregle cualquier entrada donde w , c ∈ R n + y (WLOG) S = { 1 , 2 , ... , n } . Reformulando ligeramente el problema, el objetivo es encontrar M ⊆ S de tamaño K maximizando ∑ i ∈ M w i c i( S, w , c , K) w,c∈Rn+ S={1,2,…,n} M⊆S K .∑i∈Mwici∑i∈Mci−∑i∈Mwi
Particionando las posibles soluciones para en las que contienen las que no, obtenemos la recurrencia Dejamos los casos límite como un ejercicio.m ϕ ( d 1 , d 2 , k , m ) = max { ϕ ( d 1 , d 2ϕ(d1,d2,k,m) m
El número de subproblemas es , y para cada uno el lado derecho de la recurrencia se puede evaluar en un tiempo constante, por lo que se ejecuta el algoritmo en el polinomio de tiempo en y . n D ◻O(n2D2) n D □
Corolario. A menos que P = NP, cualquier reducción que muestre la dureza de NP se reducirá a instancias donde no es polinomial en .nD n
Observación. A menos que me equivoque, también hay un PTAS para el problema en la publicación, basado en redondear los y luego usar la programación dinámica. Sin embargo, la existencia de un PTAS no tiene relación directa con si el problema es NP-duro, como se preguntó en el post.wi
También tengo curiosidad --- ¿Alguien sabe si el caso especial cuando (para cada ) tiene un algoritmo de poli-tiempo? (EDITAR: sí, según el comentario de Willard Zhan, esto parece optimizado al tomar para contener los elementos más grandes). i M kwi=ci i M k
fuente
¿Está preguntando acerca de la maximización de una función sin restricciones?
Es realmente simple Si M es el conjunto más grande, entonces es la mejor solución. No es necesario calcular nada.
Este problema parece similar al problema de la mochila, que es NP por cierto.
fuente