¿Este problema es NP-difícil?

Question

Estoy tratando de encontrar un algoritmo razonable para este problema:

Digamos que tiene un montón de bolas. Cada pelota tiene al menos un color, pero también puede ser multicolor. Cada pelota también tiene un número en ella. También hay un montón de cajas que tienen un solo color. El objetivo es maximizar la suma de los números de las bolas en las cajas, y las únicas reglas son:

• con el fin de colocar una bola en una caja, que tiene que tener al menos el color del cuadro de en él
• solo puede poner una pelota en cada caja .

Por ejemplo, se puede poner una bola azul y verde en una caja azul o una caja verde, pero no en una caja roja.

He encontrado algunas optimizaciones que ayudan mucho en términos de tiempo de ejecución. Por ejemplo, puede clasificar las bolas en orden descendente de valor de punto. Luego, a medida que pasa del número más alto al más bajo, si la bola solo tiene un color y no hay otras bolas de punto más alto que contengan ese color, puede colocarlo en esa casilla (y así eliminar esa caja y esa bola del combinaciones restantes).

Solo tengo curiosidad por saber si hay algún tipo de algoritmo dinámico para este tipo de problema, o si es solo el problema del vendedor ambulante disfrazado. ¿Ayudaría si supiera que hay como mucho X colores? Cualquier ayuda es muy apreciada. ¡Gracias!

---

Editar - aquí está un ejemplo sencillo:

Bolas:

• 1 bola roja - 5 puntos
• 1 bola azul - 3 puntos
• 1 verde/bola roja - 2 puntos
• 1 bola verde/azul - 4 puntos
• 1 rojo/azul de la bola - 1 punto

Cajas:

• 1 rojo
• 1 azul
• 1 verde

óptima Solución:

• roja bola en caja roja
• bola azul en caja azul

• bola verde/azul en caja verde

  valor Total: 12 puntos (5 + 3 + 4)

Answer 1

Este es un caso especial de el maximum weight matching problem on a weighted bipartite graph.Construye un gráfico cuyos vértices izquierdos corresponden a bolas, cuyos vértices derechos corresponden a cajas y con el borde uniendo una bola y una caja con peso V donde V es el número en la bola si la pelota puede colocarse en la caja, y 0 . Agregue cajas o bolas adicionales unidas al otro lado con bordes de peso cero hasta que tenga el mismo número de vértices en cada lado. La asignación que está buscando está determinada por el conjunto de bordes de peso distinto de cero en la coincidencia de peso máximo (total) en el gráfico resultante.

El algoritmo de asignación se puede resolver en O (n^3) tiempo, donde n es aquí el número máximo de bolas o cajas, usando Hungarian algorithm. (Por cierto, debo aclarar que solo menciono el algoritmo húngaro porque es el resultado teórico con el que estoy familiarizado y presumiblemente responde la pregunta en el título de si el problema original es NP-hard. No tengo idea si es el mejor algoritmo para usar en la práctica.)

Answer 2

¿Ha probado una alg codiciosos? Ordene por puntos/valor y colóquelo en la casilla si es posible. Si me faltan algunas excepciones, me gustaría verlas.